计算器表达式求值算法-CSDN博客

本文链接：https://blog.csdn.net/chenyang890/article/details/70169904

表达式求值

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 4

描述

ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。
比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

输入

第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0

输出

每组都输出该组运算式的运算结果，输出结果保留两位小数。

样例输入

2
1.000+2/4=
((1+2)*5+1)/4=

样例输出

1.50
4.00

解题思路

解这道题首先要对栈有所了解，可以先做一下http://acm.nyist.net/JudgeOnline/problem.php?pid=305，对这类题的处理方法有所了解，这两道题我用的处理方法原理是一致的，可以先了解一下上一道题的题解http://blog.csdn.net/chenyang890/article/details/70161305。

这道题首先我利用两个栈，一个存操作数，一个存操作符，基于上一题的理解，可以很快理解这道题的思路，不同的是，这道题我们要自己定义符号的优先级，还要对小数处理好，小数的处理我是分成了整数部分和小数点后面部分进行处理的。

这类题最基本还是要处理好栈顶元素的优先级和当前符号的优先级的不同关系的不同情况

主要看代码注释吧

解题代码

#include<iostream>
#include<stdio.h>
#include<stack>
#include<string.h>
#include<math.h>
using namespace std;
int priority(char a)//定义优先级
{
    if(a=='+'||a=='-')
        return 1;
    if(a=='*'||a=='/')
        return 2;
    if(a=='('||a==')')
        return 0;
    if(a=='#')
        return -1;
}
double require(double a,double b,char c)//对操作数进行处理
{
    double ans;
    if(c=='+')
        return a+b;
    if(c=='-')
        return b-a;
    if(c=='*')
        return a*b;
    if(c=='/')
        return b/a;
}
int main()
{
    int T;
    scanf("%d",&T);
    char ch[1005];
    while(T--)
    {
        stack<char> S;
        stack<double> Q;
        memset(ch,0,sizeof(ch));
        scanf("%s",ch);
        int len1=strlen(ch);
        double ans1;
        for(int i=0;i<len1-1;i++)//对最后一个字符=不进行处理
        {
            int l=0;
            ans1=0;
            if(ch[i]>='0'&&ch[i]<='9')//这里面是对整数或者小数的处理
            {
                double ans=ch[i]-'0';
                int j=i+1;
                while(1)
                {
                    if(ch[j]>='0'&&ch[j]<='9')
                    {
                        ans=ans*10+ch[j]-'0';
                        j++;
                    }
                    else if(ch[j]=='.')//处理小数点后面部分
                    {
                        j=j+1;
                        l=0;//记录小数点后面的位数
                        ans1=0;
                        while(1)
                        {

                            if(ch[j]>='0'&&ch[j]<='9')
                            {
                                ans1=ans1*10+ch[j]-'0';
                                j++;
                                l++;
                            }
                            else
                                break;
                        }
                    }
                    else
                    {
                        i=j;
                        break;
                    }
                }
                i--;
               ans=ans+1/(pow(10.0,(double)l))*ans1;
                Q.push(ans);//将操作数入栈
            }
            else if(priority(S.top())<priority(ch[i])||ch[i]=='(')//如果遇到左括号要直接入队，当前符号优先级大于等于栈顶符号优先级时入队
            {
                S.push(ch[i]);
            }
            else//当前栈顶符号的优先级大于当前符号优先级时要处理操作数
            {
                while(priority(ch[i])<=priority(S.top()))//要一直出栈到当前符号的优先级大于栈顶元素时
                {
                    if(S.top()=='(')//出栈到第一个左括号
                    {
                        S.pop();
                        break;
                    }
                    double a=Q.top();
                    Q.pop();
                    double b=Q.top();
                    Q.pop();

                    double c=require(a,b,S.top());
                    S.pop();
                    Q.push(c);//得到的操作数入队

                }
                if(ch[i]!=')')//如果当前符号不是')'，当前操作符也要直接入队，小细节不可忘记
                    S.push(ch[i]);

            }
        }
        //结束后由于最后一个=没处理，所以操作数栈还不止一个操作数
        while(S.top()!='#')
        {
            double a=Q.top();
            Q.pop();
            double b=Q.top();
            Q.pop();
            double c=require(a,b,S.top());
            S.pop();
            Q.push(c);
        }
       printf("%.2lf\n",Q.top());
    }
    return 0;
}