美文网首页
栈的应用——2. 简单计算器

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

作者: 辘轳鹿鹿 | 来源:发表于2020-07-14 10:19 被阅读0次

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

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

输出

3.00
13.36

解题心得:

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

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

}


相关文章

网友评论

      本文标题:栈的应用——2. 简单计算器

      本文链接:https://www.haomeiwen.com/subject/zfzaqktx.html