栈的应用——2. 简单计算器

题目描述

读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

输入描述:

测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出描述:

对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

示例1

输入

1 + 2
4 + 2 * 5 - 7 / 11
0

输出

3.00
13.36

解题心得：

• 利用堆栈对表达式求值的方法：

  • 1. 设立两个堆栈，一个用来保存运算符，另一个用来保存数字。
  • 2. 在表达式首尾添加标记运算符，该运算符运算优先级最低
  • 3. 从左至右依次遍历字符串，若遍历到运算符，则将其与运算符栈栈顶元素进行比较，若运算符栈栈顶运算符优先级小于该运算符或者此时运算符栈为空，则将该运算符压入堆栈。遍历字符串中下一个元素。
  • 4. 若运算符栈栈顶运算符优先级大于该运算符，则弹出该栈顶运算符，再从数字栈中依次弹出两个栈顶数字，完成弹出的运算符对应的运算得到结果后，再将该结果压入数字栈，重复比较此时栈顶运算符与当前遍历到的运算符优先级，视其优先级大小重复步骤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;

}