Responsive image

问题 A: 第1关:基于栈的中缀算术表达式求值

问题 A: 第1关:基于栈的中缀算术表达式求值

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 154
[提交][状态][讨论版][命题人:]

题目描述

本关任务:输入一个中缀算术表达式,求解表达式的值。运算符包括+、-、*、/、(、)、=,参加运算的数为double类型且为正数。(要求:直接针对中缀算术表达式进行计算,不能转换为后缀或前缀表达式再进行计算,只考虑二元运算即可。)

#include <iostream>
#include<iomanip>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef struct
{//运算符栈
    char *base;
char *top;
int stacksize;
}SqStack1;
int InitStack1(SqStack1 &S)
{//运算符栈初始化
S.base=new char[MAXSIZE];
if(!S.base) return OVERFLOW;
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}
int Push1(SqStack1 &S, char e)
{//运算符栈入栈
if(S.top-S.base==S.stacksize)  //栈满
return ERROR;
*S.top=e;
S.top++;
return OK;
}
int Pop1(SqStack1 &S)
{//运算符栈出栈
if(S.top==S.base)      //栈空
return ERROR;
S.top--;
return OK;
}
char GetTop1(SqStack1 S)
{//运算符栈取栈顶元素
if(S.top!=S.base)
return *(S.top-1);
  return ERROR;
}
typedef struct
{//操作数栈
double *base;
double *top;
int  stacksize;
}SqStack2;
int InitStack2(SqStack2 &S)
{//操作数栈初始化
S.base=new double[MAXSIZE];
if(!S.base) return OVERFLOW;
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}
int Push2(SqStack2 &S,double e)
{//操作数栈入栈
if(S.top-S.base==S.stacksize)     //栈满
        return ERROR;
*S.top=e;
S.top++;
return OK;
}
int Pop2(SqStack2 &S)
{//操作数栈出栈
if(S.top==S.base)           //栈空
return ERROR;
S.top--;
return OK;
}
double GetTop2(SqStack2 S)
{//操作数栈取栈顶元素
if(S.top!=S.base)
return *(S.top-1);
  return ERROR;
}
double Calculate(double a,char op,double b)
{//计算表达式“a op b”的值
    switch(op)
    {
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
    }
}

char Precede(char a,char b)
{//比较运算符a和b的优先级
if((a=='('&&b==')')||(a=='='&&b=='='))
return '=';
else if(a=='('||a=='='||b=='('||(a=='+'||a=='-')&&(b=='*'||b=='/'))
return '<';
else
return '>';
}


double Evaluateexpression(SqStack1 OPTR,SqStack2 OPND,char s[])
{//算术表达式求值的算符优先算法
/**************begin************/

 

/**************end************/
}


int main()
{//设OPTR和OPND分别为运算符栈和操作数栈
SqStack1 OPTR;
InitStack1(OPTR);    //初始化OPND栈
SqStack2 OPND;
InitStack2(OPND);    //初始化OPTR栈
Push1(OPTR,'=');     //将表达式起始符“=”压入OPTR栈        
char s[100];
while(cin>>s)
{//循环读入多组数据
if(s[0]=='=') 
   break;    //当表达式只有一个“=”时,输入结束 
//输出中缀算术表达式的值
cout<<fixed<<setprecision(2)<<Evaluateexpression(OPTR,OPND,s)<<fixed<<setprecision(2)<<endl;

}
return 0;
}













输入描述

多组数据,每组数据一行,对应一个算术表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。参加运算的数为double类型。

输出描述

对于每组数据输出一行,为表达式的运算结果。输出保留两位小数。

样例输入

2+2=
20*(4.5-3)=
=

样例输出

4.00
30.00

提示

组合提交代码,你仅需要提交



double Evaluateexpression(SqStack1 OPTR,SqStack2 OPND,char s[])

{//算术表达式求值的算符优先算法

/**************begin************/



 



/**************end************/

}








[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版