当前位置: 代码迷 >> 综合 >> 第九届省赛题 表达式求值
  详细解决方案

第九届省赛题 表达式求值

热度:44   发布时间:2024-01-16 20:18:01.0

表达式求值

时间限制: 1000 ms  |  内存限制: 65535 KB
难度: 3
描述
假设表达式定义为: 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(a,b)的形式,所以我们忽略掉Smax四个字符,直接处理检索到的“(”“,”“)”,也就是说将这个函数中的括号和其他括号统一规则处理,而将逗号和加号、乘号划为一类来处理。注意优先级问题即可。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
char ch[1010];
int chang,a,b;
stack<int >shu;   //用来保存数的栈
stack<char >fu;   //用来保存符号的栈
int sMax(int x,int y)   //计算出Smax中的最大值
{int sumX=0;int sumY=0;while(x){sumX=sumX+x%10;x=x/10;}while(y){sumY=sumY+y%10;y=y/10;}return sumX>sumY?sumX:sumY;}
int getNum(int *k)  //算出数的值
{int num=0;while(ch[*k]>='0'&&ch[*k]<='9'){num=num*10+ch[(*k)]-'0';(*k)++;}(*k)--;// printf("%d  %d****\n",*k,num);return num;
}
int main()
{int t;scanf("%d",&t);while(t--){getchar();int i;cin>>ch;chang=strlen(ch);for(i=0;i<chang;i++){if(ch[i]>='0'&&ch[i]<='9')shu.push(getNum(&i));else if(ch[i]=='S')i=i+3;else if(ch[i]==')'){while(!fu.empty()&&fu.top()!='('){int numA=shu.top();shu.pop();int numB=shu.top();shu.pop();int num;switch(fu.top()){case '+':num=numA+numB;break;case '*':num=numA*numB;break;case ',':num=sMax(numA,numB);break;}shu.push(num);fu.pop();}fu.pop();}else if(ch[i]==','||ch[i]=='+'&&!fu.empty()&&fu.top()=='*'){while(!fu.empty()&&fu.top()!='('){int numA=shu.top();shu.pop();int numB=shu.top();shu.pop();int num;switch(fu.top()){case'+':num=numA+numB;break;case'*':num=numA*numB;break;}shu.push(num);fu.pop();}fu.push(ch[i]);}else if(ch[i]=='+'||ch[i]=='*'||ch[i]==','||ch[i]=='('){fu.push(ch[i]);}}while(!fu.empty()){int numA=shu.top();shu.pop();int numB=shu.top();shu.pop();int num;switch(fu.top()){case'+':num=numA+numB;break;case'*':num=numA*numB;break;case',':num=sMax(numA,numB);break;}shu.push(num);fu.pop();}int s=shu.top();printf("%d\n",s);}return 0;
}


  相关解决方案