表达式求值

题目描述

假设表达式定义为:
1. 一个十进制的正整数 X 是一个表达式。
2. 如果 X 和 Y 是 表达式，则 X+Y, X*Y 也是表达式; *优先级高于+.
3. 如果 X 和 Y 是 表达式，则 函数 Smax(X,Y)也是表达式,其值为:先分别求出 X ,Y
值的各位数字之和，再从中选最大数。
4．如果 X 是 表达式，则 （X）也是表达式。
例如:
表达式 12*(2+3)+Smax(333,220+280) 的值为 69。
请你编程，对给定的表达式，输出其值。

输入

第一行： T 表示要计算的表达式个数 （$1 \le T \le 10$）
接下来有 T 行， 每行是一个字符串，表示待求的表达式，长度<=1000

输出

对于每个表达式，输出一行，表示对应表达式的值。

样例输入 Copy

3
12+2*3
12*(2+3)
12*(2+3)+Smax(333,220+280) 

样例输出 Copy

18
60
69

解题思路：

这道题主要是考察利用栈求表达式。要分清运算符号的优先级。“ * ”优先级最高，遍历到“ * ”，就把栈顶的所有“ * ”“ + ”都计算出来。遍历到" + ",就把栈顶的所有“ * ”都计算出来。遍历到" , "因为要计算后面的表达式，所以要让“ ，”进栈，优先级高于“ ）”。

AC代码：

#include<iostream>
#include<stack>
#include<string>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		stack<int> a;//数据栈 
		stack<char> b;//符号栈 
		string s;
		cin>>s;
		s="("+s+")";
//		cout<<s<<endl;
		for(int i=0;i<s.length();i++)
		{
			if(s[i]=='(')
				b.push('(');
			else if(s[i]==')'||s[i]==',')
			{
				while(b.top()!='(')
				{
					int a1=a.top(); a.pop();
					int a2=a.top(); a.pop();
					if(b.top()=='+')
						a.push(a1+a2);
					else if(b.top()=='*')
						a.push(a1*a2);
					else if(b.top()==',')
					{
						int sumb=0,suma=0;
						while(a1!=0)
						{
							suma+=a1%10;
							a1/=10;
						}
						while(a2!=0)
						{
							sumb+=a2%10;
							a2/=10;
						}
						a.push(max(sumb,suma));
					}
					b.pop();
				}
				b.pop();
				if(s[i]==',') b.push(',');
			}
			else if(s[i]=='+')
			{
				while(b.top()!='('&&b.top()!=',')
				{
					int a1=a.top(); a.pop();
					int a2=a.top(); a.pop();
					if(b.top()=='+')
						a.push(a1+a2);
					else
						a.push(a1*a2);					
					b.pop();
				}
				b.push('+');
			}
			else if(s[i]=='*')
			{
				while(b.top()=='*')
				{
					int a1=a.top(); a.pop();
					int a2=a.top(); a.pop();
					a.push(a1*a2);
					b.pop();
				}
				b.push('*');
			}
			else if(isdigit(s[i]))
			{
				int t=0;
				while(isdigit(s[i]))
					t=t*10+s[i++]-'0';
				i--;
				a.push(t);
			}
			else if(s[i]=='S')
			{
				b.push('(');
				i+=3;
			}
		}
		cout<<a.top()<<endl;
		a.pop();
	} 
	return 0;
}