首页 > 代码库 > 后缀表达式求值

后缀表达式求值

#include<iostream>
#include<stack>
#include<cstring>
#include<string>
using namespace std;
int judge(char popx,char x);
int func(string String,int *i);
int calculate(int x,int y,char str); 
int main()
{
int n,i;
char a[6000];
stack<char>str;
str.push(‘#‘);
cin>>n;
while(n--)
{
cin>>a;
string substr="";
int j;
for(i=0;i<strlen(a);)
{
if(a[i]-‘0‘>=0&&a[i]-‘0‘<=9)
{
for(j=i;a[j]-‘0‘>=0&&a[j]-‘0‘<=9;j++)
substr+=a[j];
substr+=‘ ‘;
i=j;
}
else
{
if(judge(str.top(),a[i])==1)
{
substr+=str.top();
                    str.pop();
}
else
if(judge(str.top(),a[i])==2)
{
str.push(a[i]);
i++;
}
else
if(judge(str.top(),a[i])==3)
{
str.pop();
i++;
}
}
}
while(str.top()!=‘#‘)
{
substr+=str.top();
str.pop();
}
stack<int>stack1;
cout<<substr<<endl;
for(i=0;i<substr.length();i++)
{
int num=0;
if(substr[i]-‘0‘>=0&&substr[i]-‘0‘<=9)
stack1.push(func(substr,&i));
else
{
int num1=stack1.top();
stack1.pop();
int num2=stack1.top();
stack1.pop();
stack1.push(calculate(num2,num1,substr[i]));
}
}
cout<<stack1.top()<<endl;
stack1.pop();
}
}
int judge(char popx,char x)
{
if(popx==‘*‘||popx==‘/‘)
{
if(x==‘*‘||x==‘/‘||x==‘+‘||x==‘-‘||x==‘)‘)   //输出 
return 1;
else
if(x==‘(‘)                                //入栈 
return  2;
}
else
if(popx==‘+‘||popx==‘-‘)
   {
if(x==‘*‘||x==‘/‘||x==‘(‘)
return 2;
else
if(x==‘+‘||x==‘-‘||x==‘)‘)
return 1;
}
else
if(popx==‘(‘&&x!=‘)‘)
return 2;
else
if(popx==‘(‘&&x==‘)‘)
return 3;                                         //出栈后移 
else
if(popx==‘#‘)
return 2;
}


int calculate(int x,int y,char str)
{
if(str==‘+‘)
return x+y;
else
if(str==‘-‘)
return x-y;
else
if(str==‘*‘)
return x*y;
else
if(str==‘/‘)
return x/y;
}
int func(string String,int *i)
{
int j,num=0;
for(j=*i;String[j]-‘0‘>=0&&String[j]-‘0‘<=9&&String[j]!=‘ ‘;j++)
{
num=num*10+(String[j]-‘0‘);
}
*i=j;
return num;
}

后缀表达式求值