题目描述:
假设表达式定义为: 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≤ T ≤ 10) 接下来有 T 行, 每行是一个字符串,表示待求的表达式,长度<=1000
输出描述:
【标准输出】 对于每个表达式,输出一行,表示对应表达式的值。
样例输入:
复制
3 12+2*3 12*(2+3) 12*(2+3)+Smax(333,220+280)
样例输出:
18 60 69
这道题和基本的表达式求值最主要的区别在于多了一个smax运算,其实也非常简单,只需要在运算时将smax中的逗号作为smax函数的运算符,并在自己编写的运算函数mathnum中加入此运算即可
解题代码;
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
int smax(int x,int y){//判断smax,并返回较大的数
int m1=0,m2=0;
while(x>0){
m1+=x%10;
x/=10;
}
while(y>0){
m2+=y%10;
y/=10;
}
if(m2>m1)return m2;
return m1;
}
double mathnum(double x,double y,char ss){ //此函数用来运算当前步骤,根据不同的符号返回不同的结果
if(ss=='+')return x+y;
if(ss=='-')return y-x;
if(ss=='*')return x*y;
if(ss=='/')return y/x;
if(ss==',')return smax(x,y);
}
int bj[6][6]{ //因为在ASC码表中 *+,-/分别为74 75 76 77 79 所以对应优先表建为这样 bj[i][j]中i代表字符栈顶端的字符,j代表当前字符,若其值为1则代表应将栈顶字符优先使用
{1,1,1,1,0,1},
{0,1,1,1,0,0},
{0,0,0,0,0,0},
{0,1,1,1,0,0},
{0,0,0,0,0,0}, //第四行以及第四列因为78对应的字符于运算无关,所以全部设为零
{1,1,1,1,0,1}
};
int main()
{
int t;
cin>>t;
while(t--){
stack<char> sl; //符号栈
stack<double> nnum; //数字栈
int num1=0;
char sstr[1005];
cin>>sstr;
for(int i=0;i<strlen(sstr);i++){
if(sstr[i]>='0'&&sstr[i]<='9')num1=num1*10+(sstr[i]-'0'); //若一直是数字,则一直乘
else{
if(sstr[i-1]>='0'&&sstr[i-1]<='9')nnum.push(num1); //若此位不是数字且上一位是,则将num1加入到数字栈nnum中
num1=0;
if(sstr[i]=='S')i+=4; //如果此位等于S,说明就是smax函数,但是此题我准备使用中间的逗号,来表示smax函数,
if(sstr[i]=='('||sl.empty()||sl.top()=='('){ //这三种特殊的情况直接将字符加入到字符栈
sl.push(sstr[i]);continue;
}
else if(sstr[i]==')'){ //如果是右括号,则 一直将其运算到左括号
double num2=nnum.top();
nnum.pop();
while(sl.top()!='(') {
num2=mathnum(num2,nnum.top(),sl.top());
sl.pop();
nnum.pop();
}
nnum.push(num2);
sl.pop();
continue;
}
int p1=sl.top()-'*',p2=sstr[i]-'*'; //若并非以上特殊情况则说明此位符号和符号栈栈顶符号均不是括号,则根据优先级判定如何计算
if(!bj[p1][p2])sl.push(sstr[i]); //若此位优先级高,则直接将此位符号加入到符号栈
else {
while(bj[p1][p2]){ //若不是则直接一直运算到栈顶符号优先级高于此位为止
double num2=nnum.top();
nnum.pop();
num2=mathnum(num2,nnum.top(),sl.top());
nnum.pop();
nnum.push(num2);
sl.pop();
if(!sl.empty())p1=sl.top()-'*'; //这个地方一定特别注意,因为可能此时将栈顶元素清除后,符号栈已经为空了
else break;
}
sl.push(sstr[i]);
}
}
}
if(sstr[strlen(sstr)-1]>='0'&&sstr[strlen(sstr)-1]<='9'){ //因为上面我们等到此位不为数字时才将前面的数字加入数字栈,但有可能算数表达式最后一个是数字,这样的话,按照上面的程序就还有最后一个数没有加入到数字栈中
nnum.push(num1);
}
while(!sl.empty()){
double num2=nnum.top();
nnum.pop();
num2=mathnum(num2,nnum.top(),sl.top());
nnum.pop();
sl.pop();
nnum.push(num2);
}
cout<<nnum.top()<<endl;
}
return 0;
}