题目描述
读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。
输入描述:
测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。
输出描述:
对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。
示例1
输入
1 + 2
4 + 2 * 5 - 7 / 11
0
输出
3.00
13.36
解题心得:
-
利用堆栈对表达式求值的方法:
- 设立两个堆栈,一个用来保存运算符,另一个用来保存数字。
- 在表达式首尾添加标记运算符,该运算符运算优先级最低
- 从左至右依次遍历字符串,若遍历到运算符,则将其与运算符栈栈顶元素进行比较,若运算符栈栈顶运算符优先级小于该运算符或者此时运算符栈为空,则将该运算符压入堆栈。遍历字符串中下一个元素。
- 若运算符栈栈顶运算符优先级大于该运算符,则弹出该栈顶运算符,再从数字栈中依次弹出两个栈顶数字,完成弹出的运算符对应的运算得到结果后,再将该结果压入数字栈,重复比较此时栈顶运算符与当前遍历到的运算符优先级,视其优先级大小重复步骤3或步骤4。
-
遇到错误如何解决:
- 一般程序打印不出来结果,可能是循环的条件设置的有问题。多使用printf输出中间结果。
- scanf("%s")方式输入字符串是以空格为分隔符;gets(str)是以换行符为分隔符。
- 注意题目对输出格式的要求。
- 对于运算符的优先级,也可预先保存在0-1矩阵中。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main(){
char str[202];
double stack1[202];
char stack2[202];
while(gets(str)){
int slen=strlen(str),i,flag=0;
int top1=0,top2=0,sum=0;
if(strcmp(str,"0")==0)
break;
str[slen]=' ';
for(i=0;i<=slen;i++){
if(!flag){
if(str[i]==' '){
flag=1;
stack1[top1]=sum*1.0;
top1++;
sum=0;
}
else{
sum=sum*10;
sum+=str[i]-'0';
}
}
else{
if(str[i]==' '){
flag=0;
}
else{
if(top2==0){
stack2[top2]=str[i];
top2++;
}
else{
while((top2>0)&&!((stack2[top2-1]=='+'||stack2[top2-1]=='-')&&(str[i]=='*'||str[i]=='/'))){
top2--;
double tmp;
if(stack2[top2]=='-'){
tmp=stack1[top1-2]-stack1[top1-1];
}
else if(stack2[top2]=='*'){
tmp=stack1[top1-2]*stack1[top1-1];
}
else if(stack2[top2]=='/'){
tmp=stack1[top1-2]*1.0/stack1[top1-1];
}
else{
tmp=stack1[top1-2]+stack1[top1-1];
}
top1--;
stack1[top1-1]=tmp;
}
stack2[top2]=str[i];
top2++;
}
}
}
}
while(top2!=0){
top2--;
double tmp;
if(stack2[top2]=='-'){
tmp=stack1[top1-2]-stack1[top1-1];
}
else if(stack2[top2]=='*'){
tmp=stack1[top1-2]*stack1[top1-1];
}
else if(stack2[top2]=='/'){
tmp=stack1[top1-2]/stack1[top1-1];
}
else{
tmp=stack1[top1-2]+stack1[top1-1];
}
top1--;
stack1[top1-1]=tmp;
}
printf("%.2f\n",stack1[top1-1]);
}
return 0;
}
网友评论