栈求表达式的值(有一点问题,大家帮忙看看)
#include<iostream>using namespace std;
#define StackSize 100
template <class T>
class SqStack
{
private:
T str[StackSize];
int top;
public:
void InitStack();
int StackLength();
int IsEmpty();
void Push (T m);
void Pop(T e);
T GetTop();
};
//初始化
template <class T>
void SqStack<T>::InitStack()
{
top = -1;
}
//求栈的长度
template <class T>
int SqStack<T>::StackLength()
{
return(top+1);
}
//判断是否为空栈
template <class T>
int SqStack<T>::IsEmpty()
{
if(top=-1)
return 1;
}
//进栈
template <class T>
void SqStack<T>::Push (T m)
{
if(top!=StackSize-1)
{
top++;
str[top]=m;
}
}
//退栈
template <class T>
void SqStack<T>::Pop(T e)
{
if(top!=-1)
e=str[top];
top--;
}
//取栈顶元素
template <class T>
T SqStack<T>::GetTop()
{
return str[top];
}
//判断是运算符,数字,还是其他
int isOpMember (char ch)
{
if(ch=='0'||ch=='1'||ch=='2'||ch=='3'||ch=='4'||ch=='5'||ch=='6'||ch=='7'||ch=='8'||ch=='9')
return 0;
else if (ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='\0')
return 1;
else
return -1;
}
//各种运算符在运算符优先级矩阵对应的下标
int order (char m)
{
switch (m)
{
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
case '(':return 4;
case ')':return 5;
case '\0':return 6;
default :return 7;
}
}
//判断两运算符运算优先级
int precede (char op1,char op2)
{
int inCmpOut[7][7]={
{1,1,-1,-1,-1,1,1},
{1,1,-1,-1,-1,1,1},
{1,1,1,1,-1,1,1},
{1,1,1,1,-1,1,1},
{-1,-1,-1,-1,-1,0,0},
{1,1,1,1,2,1,1},
{-1,-1,-1,-1,-1,2,0}
};
int i,j;
i=order (op1);
j=order (op2);
return inCmpOut [i][j];
}
//把中缀表达式转化为后缀表达式
void transform ( char * midS,char * suffixS)
{
int i=0;
int j=0;
char ch = midS[0];
SqStack<char>s;
s.InitStack();
char op;
s.Push ('\0');
while (!s.IsEmpty())
{
if(!isOpMember(ch))
{
if(i>0 && isOpMember( suffixS[i-1]=1))
suffixS[i++]=' ';
suffixS[i++]=ch;
}
else
{
if( i>0 && suffixS[i-1] != ' ')
suffixS[i++]=' ';
switch ( ch )
{
case '(':s.Push(ch);break;
case ')':s.Pop(op);
while(op!='(')
{
suffixS[i++]=op;
suffixS[i++]=' ';
s.Pop(op);
}
--i;
break;
default:
while(op=s.GetTop())
{
if(precede(op,ch)==1||precede(op,ch)==0)
{
suffixS[i++]=op;
suffixS[i++]=' ';
}
else
break;
s.Pop(op);
}
if(ch!='\0')
s.Push(ch);
break;
}
}
if(ch!='\0')
ch=midS[++j];
}
suffixS[i]='\0';
}
//指定运算符的运算
double caculate ( double a, char ch , double b)
{
switch (ch)
{
case '+':return a+b;
case '-':return a-b;
case '*':return a*b;
case '/':return a/b;
default: return -1;
}
}
//后缀表达式的计算
double evaluation (char * suffixS)
{
int i=0;
char ch=suffixS[i];
double x;
SqStack<double>s;
s.InitStack();
double a,b;
while (ch!='\0')
{
if(isOpMember(ch)==0)
{
x=0;
while (isOpMember(ch)==0)
{
x=10*x+(ch-'0');
ch=suffixS[++i];
}
s.Push(x);
}
else if(isOpMember(ch)==1)
{
s.Pop(b);
s.Pop(a);
s.Push(caculate(a,ch,b));
}
ch=suffixS[++i];
}
s.Pop(x);
return x;
}
int main()
{
char chm[100];
char chn[100];
cin>>chm;
transform ( chm,chn);
cout<<evaluation (chn)<<endl;
}