表达式求值(栈的应用)(C++)

表达式求值:

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

分析:

古老问题~

先分析下 4则运算规则:

1. 先乘除后加减；

2. 从左到右计算；

3. 先括号内后括号外；

于是我们要把运算符优先级确定清楚这里我只用这几个运算符:+-*/

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

这个还是用栈来实现具体代码如下

代码:

# <iostream>

# <>

using std;

const STACK_INIT_SIZE=100; //The maximize length of stack

template < T> Stack //A of stack

{

public:

Stack //Constructor function

{

base = [STACK_INIT_SIZE];

(!base)

{

cerr<<"Fail to assign memory!"<<endl;

exit(-1);

}

top=base;

stacksize=STACK_INIT_SIZE;

}

~Stack //Destructor function

{

(base) delete base;

}

T GetTop

{

(topbase)

{

cerr<<"Empty!"<<endl;

exit(-1);

}

*(top-1);

}

void Push(T e)

{

(top-base>=stacksize)

{

base= [STACK_INIT_SIZE];

(!base)

{

cerr<<"Fail to assign memory!"<<endl;

exit(-1);

}

top=base+STACK_INIT_SIZE;

stacksizeSTACK_INIT_SIZE;

}

*top+e;

}



void Pop(T& e)

{

(topbase)

{

cerr<<"Empty!"<<endl;

exit(-1);

}

e=*--top;

}

private:

*base;

*top;

stacksize;

};



op("+-*/#"); //The of operator



bool In(char c, op) //Judge the character whether belong to the of operator

{

::iterator iter=op.begin;

for (;iter!=op.end;iter)

(*iterc) true;

false;

}



char Precede(char top,char c) //Confirm the precedence of operator

{

grade_top=0,grade_c=0;

switch (top)

{

'#':grade_top=0;;

')':grade_top=1;;

'+':grade_top=2;;

'-':grade_top=2;;

'*':grade_top=3;;

'/':grade_top=3;;

'(':grade_top=4;;

}

switch (c)

{

'#':grade_c=0;;

')':grade_c=1;;

'+':grade_c=2;;

'-':grade_c=2;;

'*':grade_c=3;;

'/':grade_c=3;;

'(':grade_c=4;;

}



(grade_top>=grade_c) {

(top'('&&c!=')')

'<';

(top'('&&c')')

'=';

'>';

}

(top'#'&&c'#') '=';

'<';

}



Operate( a,char theta, b) //Calculate

{

(theta'+') a+b;

(theta'-') a-b;

(theta'*') a*b;

(theta'/') a/b;

0;

}



EvaluateExpression(Stack<char>& OPTR,Stack<>& OPND)

{

a=0,b=0,n=0;

char x;

char theta;

c;

cin>>c;

OPTR.Push('#');

while (c[0]!='#'||OPTR.GetTop!='#')

{

(!In(c[0],op)){

n=atoi(&c[0]);

OPND.Push(n);

cin>>c;

}



switch (Precede(OPTR.GetTop,c[0]))

{

'<':

OPTR.Push(c[0]);

cin>>c;

;

'=':

OPTR.Pop(x);

cin>>c;

;

'>':

OPTR.Pop(theta);

OPND.Pop(b);

OPND.Pop(a);

OPND.Push(Operate(a,theta,b));

;

}

}

OPND.GetTop;

}





{

Stack<char> OPTR;

Stack<> OPND;

cout<<"Please input your expression,end of '#':"<<endl;

cout<<EvaluateExpression(OPTR,OPND)<<endl;

0;

}

延伸阅读