算法训练 表达式计算
程序员文章站
2022-06-26 08:47:32
...
问题描述
输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除。
输入格式
输入一行,包含一个表达式。
输出格式
输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定
表达式长度不超过100,表达式运算合法且运算过程都在int内进行。
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=10010;
char str[maxn];
char s[maxn];
int val[maxn];
stack<int> shu;
stack<char> fu;
int solve(int num1,int num2,char ch){
if(ch=='-')return num1-num2;
if(ch=='+')return num1+num2;
if(ch=='*')return num1*num2;
if(ch=='/')return num1/num2;
printf("****\n");
return -1;
}
int cmp(char c1,char c2){
if(c1=='('||c2=='(')return 0;
if(c1=='+'||c1=='-')return 1;
if(c1=='*'&&(c2=='*'||c2=='/'))return 1;
if(c1=='/'&&(c2=='*'||c2=='/'))return 1;
return 0;
}
//1+((23+34)*5)-6
/*
学习了一种逆波兰表达式,就是中序转换成后序
如果是数字的话,直接输出到表达式里面,如果是优先级大于栈顶的话,是直接放入的,包括'('
,如果是')',我们是一直冒到第一个'('为止
*/
int main()
{
memset(s,0,sizeof(s));
scanf("%s",str);
int len=strlen(str);
str[len]=')';
int cur=0;
fu.push('(');//一开始就往栈里面放一个'(',最后在放一个')',这样的话,就不用后面的那个 while()来清栈了
for(int i=0;i<=len;){
if(str[i]>='0'&&str[i]<='9'){
int sum=0;
while(i<len&&str[i]>='0'&&str[i]<='9'){
sum=sum*10+str[i]-'0';
i++;
}
val[cur++]=sum;
}
else{
if(str[i]==')'){
while(!fu.empty()&&fu.top()!='('){
s[cur++]=fu.top();
// printf("**%c\n",fu.top());
fu.pop();
}
fu.pop();
}
else{
while(!fu.empty()&&cmp(str[i],fu.top())){
s[cur++]=fu.top();
fu.pop();
}
fu.push(str[i]);
}
i++;
}
}
/*
for(int i=0;i<cur;i++){
if(s[i])printf("%c ",s[i]);
else printf("%d ",val[i]);
}
printf("****\n");
*/
for(int i=0;i<cur;i++){
if(!s[i])
shu.push(val[i]);
else{
int v2=shu.top();shu.pop();
int v1=shu.top();shu.pop();
int v=solve(v1,v2,s[i]);
shu.push(v);
}
}
printf("%d\n",shu.top());
return 0;
}