-
描述
-
人们熟悉的四则运算表达式称为中缀表达式，例如(23+34*45/(5+6+7))。在程序设计语言中，可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到表达式的值。
给定一个中缀表达式，编写程序，利用堆栈的方法，计算表达式的值。
-
输入
-
第一行为测试数据的组数N
接下来的N行，每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号，操作数都是正整数，数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。
-
输出
-
对每一组测试数据输出一行，为表达式的值
-
样例输入
-
3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))
-
样例输出
-
43
64
108
-
提示
-
注意：运算过程均为整数运算（除法运算'/'即按照C++定义的int除以int的结果，测试数据不会出现除数为0的情况），输出结果也为整数（可能为负）。
中间计算结果可能为负。
-
# include<iostream>
# include<stdlib.h>
# include<string.h>
# include<stdio.h>
# include<stack>
using namespace std;
stack<char> q;
stack<int> w;
bool precede(char a,char b)//比较操作符优先级
{
int na,nb;
switch(a)
{
case '#':na=-1;break;
case '(':na=0;break;
case '+':
case '-':na=1;break;
case ')':
case '*':
case '/':na=2; break;
}
switch(b)
{
case '#':nb=-1;break;
case '(':nb=0;break;
case '+':
case '-':nb=1;break;
case ')':
case '*':
case '/':nb=2; break;
}
if(na>=nb)
return true;
else
return false;
}
bool opmember(char ch)//判断是否是操作符
{
if(ch=='('||ch==')'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='#')
return true;
else
return false;
}
void transform(char suffix[],char exp[])//中缀式exp转后缀式suffix
{
while(!q.empty())
{
q.pop();
}
q.push('#');
char *p=exp;
char ch=*p,c;
int k=0;
while(!q.empty())
{
if(!opmember(ch))
suffix[k++]=ch;
else{
suffix[k++]=' ';
switch(ch)
{
case '(':q.push(ch);break;
case ')':{
c=q.top();
q.pop();
while(c!='(')
{
suffix[k++]=c;
c=q.top();q.pop();
}
break;
}
default:{
while(!q.empty())
{
c=q.top();
if(precede(c,ch))
{
suffix[k++]=c; q.pop();
}
else
{
break;
}
}
if(ch!='#') q.push(ch);
break;
}
}
}
if(ch!='#')ch=*++p;
}
suffix[k]='\0';
}
int operate(int a,char ch,int b)//一次计算
{
if(ch=='+')
return a+b;
else if(ch=='-')
return a-b;
else if(ch=='*')
return a*b;
else
return a/b;
}
int evaluation(char suffix[])//计算后缀式
{
char *p=suffix;
char ch=*p++;
char s[11];
int t=0,num;
int a,b,result;
while(!w.empty())
{
w.pop();
}
while(ch!='#')
{
if(!opmember(ch)&&ch!=' ')
s[t++]=ch;
else
{
if(ch==' ')
{
if(t!=0)
{
s[t]='\0';
num=atoi(s);
w.push(num);
t=0;
}
}
else
{
b=w.top();w.pop();
a=w.top();w.pop();
w.push(operate(a,ch,b));
}
}
ch=*p++;
}
result =w.top();
return result;
}
int main(void)
{
char suffix[601],exp[601];
int k;
scanf("%d",&k);
getchar();
while(k--)
{
scanf("%s",exp);
strcat(exp,"#");
transform(suffix,exp);
printf("%d\n",evaluation(suffix));
}
return 0;
}
