title: 表达式求值 第九届省赛 nyoj 1272
tags: [栈,数据结构]
题目链接
描述
假设表达式定义为: 1. 一个十进制的正整数 X 是一个表达式。 2. 如果 X 和 Y 是 表达式，则 X+Y, XY 也是表达式; *优先级高于+. 3. 如果 X 和 Y 是 表达式，则 函数 Smax(X,Y)也是表达式,其值为:先分别求出 X ,Y 值的各位数字之和，再从中选最大数。 4．如果 X 是 表达式，则 （X）也是表达式。 例如: 表达式 12(2+3)+Smax(333,220+280) 的值为 69。 请你编程，对给定的表达式，输出其值。
输入
【标准输入】 第一行： T 表示要计算的表达式个数 （1≤ T ≤ 10） 接下来有 T 行， 每行是一个字符串，表示待求的表达式，长度<=1000
输出
【标准输出】 对于每个表达式，输出一行，表示对应表达式的值。
样例输入
3
12+2*3
12*(2+3)
12*(2+3)+Smax(333,220+280)
样例输出
18
60
69
分析：
跟普通的表达式求值得算法没有什么大的区别，也是把中缀表达式转换为后缀表达式，然后用后缀表达式来求解。吧Smax也看做一种与加减乘除一样的运算，而他的优先级是最大的。
代码：
#include<bits/stdc++.h>
using namespace std;
char in[1001];///中缀
char post[1001];///后缀
int pri[200];///优先级
bool isNum(char a)///判断是不是数字
{
if(a>='0'&&a<='9')
return true;
return false;
}
void zhuan()///中缀转后缀
{
stack<char>op;
op.push('=');
int k=0,k1=0;
for(int i=0; in[i]!='\0'; i++)
{
if(in[i]=='m'||in[i]=='a'||in[i]=='x')///'S'也当作一个运算符了，这样的话就不用处理他们了
continue;
if(isNum(in[i]))
{
post[k++]=in[i];
k1++;
}
else
{
if(k1!=0)///有数字的话，就把数字分割开
{
post[k++]=' ';
k1=0;
}
if(in[i]==',')continue;///跳过，不用处理
if(in[i]=='(')
op.push(in[i]);
else if(in[i]==')')
{
while(op.top()!='(')
{
post[k++]=op.top();
op.pop();
}
op.pop();
}
else
{
while(pri[op.top()]>=pri[in[i]])
{
post[k++]=op.top();
op.pop();
}
op.push(in[i]);
}
}
}
while(op.top()!='=')
{
post[k++]=op.top();
op.pop();
}
post[k]='\0';
}
int Smax(int a,int b)///定义Smax的运算
{
int suma=0;
while(a)
{
suma+=a%10;
a/=10;
}
int sumb=0;
while(b)
{
sumb+=b%10;
b/=10;
}
return max(suma,sumb);
}
int result(int a,int b,char op)
{
switch(op)
{
case '+' :
return a+b;
case '-' :
return b-a;
case '*' :
return a*b;
case '/' :
return b/a;
case 'S' :
return Smax(a,b);
}
}
int jisuan()
{
stack<int>num;
int sum=0;
for(int i=0; post[i]; i++)
{
if(isNum(post[i]))
sum=sum*10+post[i]-'0';
else
{
if(sum!=0)
{
num.push(sum);
sum=0;
}
if(post[i]!=' ')
{
int a=num.top();
num.pop();
int b=num.top();
num.pop();
num.push(result(a,b,post[i]));
}
}
}
return num.top();
}
int main()
{
// freopen("2.txt","r",stdin);
///定义优先级，'S'表示的是Smax这个算法，优先级最大
pri['=']=0;
pri['(']=1;
pri['+']=2;
pri['-']=2;
pri['*']=3;
pri['/']=3;
pri['S']=4;
int t;
scanf("%d",&t);
while(t--)
{
memset(in,0,sizeof(in));
memset(post,0,sizeof(post));
scanf(" %s",in);
zhuan();
//puts(post);
printf("%d\n",jisuan());
}
return 0;
}