题描述
输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
输入一行，包含一个表达式。
输出格式
输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定
表达式长度不超过100，表达式运算合法且运算过程都在int内进行。
这个题的思路就是先把中缀表达式转化为后缀表达式，然后用后缀表达式计算出式子的值
1.将中缀表达式转换为后缀表达式的方法：
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从左至右扫描中缀表达式；
(3) 遇到操作数时，将其压入S2，这里由于运算数可能大于10，所以如果数字后面一个符号是运算符，则将‘#’入S2栈充当分割线；
(4) 遇到运算符时有三种情况：
(4-1) 三种情况下直接入S1栈①S1为空②运算符为‘（’③运算符优先级比S1栈顶运算符的高；
(4-2)如果右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
(4-3) 若运算符优先级小于或等于S1栈顶运算符的优先级，则依次弹出S1栈顶元素，直到运算符的优先级大于S1栈顶运算符优先级；
(6) 重复步骤(2)至(5)，直到表达式的最右边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。
运算符优先级：（乘=除）>（加=减）>（左括号=右括号）。
例：将 1 + ( ( 23 + 34 ) * 5 ) - 6转化为中缀表达式
2.后缀表达式计算方法：
（1）定义一个int栈S3，定义一个整形数组num用来存储大于10的数字便于计算，从左至右扫描表达式。
（2）遇到数字时：
（2-1）若数字后面一个元素不是#（数字后面只可能是#或数字）则将数字字符转化为数字存在num[ ]数组中；
（2-2）若数字后面一个元素是#，将num数组中保存的数字算出来并压入S3栈中。
（3）遇到运算符时，弹出S3栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如后缀表达式“1 # 2 3 # 3 4 # + 5 # * + 6 # -”：
#include<iostream>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
stack<char> s1,s2;
stack<int> s3;
char ch[150]={0};//用来存表达式
int num[11];//用来暂时存数字
int priority(char ch)//用于比较字符优先级
{
if(ch==')'||ch=='(') return 1;
if(ch=='+'||ch=='-') return 2;
if(ch=='*'||ch=='/') return 3;
}
int Scal(int x,int y,char ope)//两个数的运算
{
if(ope=='+') return x+y;
if(ope=='-') return x-y;
if(ope=='*') return x*y;
if(ope=='/'&&y!=0) return x/y;
}
void Transform(int n)//将中缀表达式转化为后缀表达式
{
int k=0;
for(int i=0;i<n;i++)
{
if(ch[i]>='0'&&ch[i]<='9')//当是数字的情况
{
if(i+1<n&&(ch[i+1]<'0'||ch[i+1]>'9')||i==n-1)//当是最后一个数字，或下一个元素是运算符
{
s2.push(ch[i]);
s2.push('#');//防止10位数数字不能统计
}
else
s2.push(ch[i]);
}
else
{
if(s1.empty()||ch[i]=='('||priority(ch[i])>priority(s1.top()))//当是运算符，有3种情况直接入栈
s1.push(ch[i]);
else if(ch[i]==')')//当是右括号的情况
{
while(s1.top()!='(')
{
s2.push(s1.top());
s1.pop();
}
s1.pop();
}
else//当运算符优先级小于或等于S1栈顶运算符的优先级
{
while(!s1.empty()&&priority(ch[i])<=priority(s1.top())&&s1.top()!='(')//这里还要注意两个界限
{
s2.push(s1.top());
s1.pop();
}
s1.push(ch[i]);
}
}
}
while(!s1.empty())//现在的结果都放在s2中
{
s2.push(s1.top());
s1.pop();
}
while(!s2.empty()) //将栈内元素放入数组里
{
ch[k++]=s2.top();
s2.pop();
}
reverse(ch,ch+k);//将ch[]反向，因为从栈出来是反的
ch[k]=0;
}
int Cal(int n)//后缀表达式计算
{
int x,y,tmp=0,k=0;
for(int i=0;i<n;i++)
{
if(ch[i]=='#')//是#直接跳过
continue;
else if(ch[i]=='+'||ch[i]=='-'||ch[i]=='*'||ch[i]=='/')//是运算符弹出栈顶两元素计算后放回栈
{
x=s3.top();
s3.pop();
y=s3.top();
s3.pop();
x=Scal(y,x,ch[i]);
s3.push(x);
}
else//是数字字符
{
if(ch[i+1]=='#')//下一个元素是#
{
num[k++]=ch[i]-'0';
for(int i=0;i<k;i++)
//如果之前不是个位数，这样可以将如23的数算出来
tmp+=(num[i]*(int)pow(10,k-i-1));
s3.push(tmp);
tmp=0;
k=0;
}
else//下一个元素不是#
{
num[k++]=ch[i]-'0';
}
}
}
return s3.top();
}
int main()
{
gets(ch);
Transform(strlen(ch));
cout<<Cal(strlen(ch))<<endl;
return 0;
}