表达式求值：

设计一个程序实现输入一个表达式如3*(3+4)，以”#”结尾，求出其值。

分析：

古老的问题~

先分析一下四则运算的规则：

1. 先乘除后加减；

2. 从左到右计算；

3. 先括号内后括号外；

于是我们要把运算符的优先级确定清楚。这里我只用这几个运算符：+-*/()，

可以知道+-的优先级低于*/，而对于()，当第一次遇到’(‘时，’(‘后面的就优先计算，直到遇到’)’为止，可以先把’(’的优先级定为比其它几个都高，然后遇到’)’时把里面的先算出来，再算括号外面的，具体实现在代码中会表现得很清楚。

这个程序还是用栈来实现，具体代码如下。

代码：

#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==