表达式求值：
设计一个程序实现输入一个表达式如3*(3+4)，以”#”结尾，求出其值。
分析：
先分析一下四则运算的规则： 1. 先乘除后加减；
2. 从左到右计算；
3. 先括号内后括号外；
于是我们要把运算符的优先级确定清楚。这里我只用这几个运算符：+-*/()，
可以知道+-的优先级低于*/，而对于()，当第一次遇到’(‘时，’(‘后面的就优先计算，直到遇到’)’为止，可以先把’(’的优先级定为比其它几个都高，然后遇到’)’时把里面的先算出来，再算括号外面的，具体实现在代码中会表现得很清楚。
考试2大提示这个程序还是用栈来实现，具体代码如下。
代码：
#include <iostream>
#include <string>
using namespace std;
const int STACK_INIT_SIZE=100; //The maximize length of stack
template <class T> class Stack //A class of stack
{
public:
Stack() //Constructor function
{
base = new int[STACK_INIT_SIZE];
if (!base)
{
cerr<<"Fail to assign memory!"<<endl;
exit(-1);
}
top=base;
stacksize=STACK_INIT_SIZE;
}
~Stack() //Destructor function
{
if (base) delete[] base;
}
T GetTop()
{
if (top==base)
{
cerr<<"Empty!"<<endl;
exit(-1);
}
return *(top-1);
}
void Push(T e)
{
if (top-base>=stacksize)
{
base=new int[STACK_INIT_SIZE];
if(!base)
{
cerr<<"Fail to assign memory!"<<endl;
exit(-1);
}
top=base+STACK_INIT_SIZE;
stacksize+=STACK_INIT_SIZE;
}
*top++=e;
}
void Pop(T& e)
{
if (top==base)
{
cerr<<"Empty!"<<endl;
exit(-1);
}
e=*--top;
}
private:
int *base;
int *top;
int stacksize;
};
string op("+-*/()#"); //The set of operator
bool In(char c,string op) //Judge the character whether belong to the set of operator
{
string::iterator iter=op.begin();
for (;iter!=op.end();++iter)
if (*iter==c) return true;
return false;
}
char Precede(char top,char c) //Confirm the precedence of operator
{
int grade_top=0,grade_c=0;
switch (top)
{
case '#':grade_top=0;break;
case ')':grade_top=1;break;
case '+':grade_top=2;break;
case '-':grade_top=2;break;
case '*':grade_top=3;break;
case '/':grade_top=3;break;
case '(':grade_top=4;break;
}
switch (c)
{
case '#':grade_c=0;break;
case ')':grade_c=1;break;
case '+':grade_c=2;break;
case '-':grade_c=2;break;
case '*':grade_c=3;break;
case '/':grade_c=3;break;
case '(':grade_c=4;break;
}
if (grade_top>=grade_c) {
if (top=='('&&c!=')')
return '<';
else if (top=='('&&c==')')
return '=';
return '>';
}
else if (top=='#'&&c=='#') return '=';
else return '<';
}
int Operate(int a,char theta,int b) //Calculate
{
if (theta=='+') return a+b;
else if (theta=='-') return a-b;
else if (theta=='*') return a*b;
else if (theta=='/') return a/b;
return 0;
}
int EvaluateExpression(Stack<char>& OPTR,Stack<int>& OPND)
{
int a=0,b=0,n=0;
char x;
char theta;
string c;
cin>>c;
OPTR.Push('#');
while (c[0]!='#'||OPTR.GetTop()!='#')
{
if (!In(c[0],op)){
n=atoi(&c[0]);
OPND.Push(n);
cin>>c;
}
else
switch (Precede(OPTR.GetTop(),c[0]))
{
case '<':
OPTR.Push(c[0]);
cin>>c;
break;
case '=':
OPTR.Pop(x);
cin>>c;
break;
case '>':
OPTR.Pop(theta);
OPND.Pop(b);
OPND.Pop(a);
OPND.Push(Operate(a,theta,b));
break;
}
}
return OPND.GetTop();
}
int main()
{
Stack<char> OPTR;
Stack<int> OPND;
cout<<"Please input your expression,end of '#':"<<endl;
cout<<EvaluateExpression(OPTR,OPND)<<endl;
return 0;
}
责任编辑：小草
