基于栈的中缀算术表达式求值

描述

输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、*、/、(、)、=，参加运算的数为double类型且为正数。（要求：直接针对中缀算术表达式进行计算，不能转换为后缀或前缀表达式再进行计算，只考虑二元运算即可。）

输入

多组数据，每组数据一行，对应一个算术表达式，每个表达式均以“=”结尾。当表达式只有一个“=”时，输入结束。参加运算的数为double类型。

输出

多组数据，每组数据一行，对应一个算术表达式，每个表达式均以“=”结尾。当表达式只有一个“=”时，输入结束。参加运算的数为double类型。

输入样例 1

2+2=
20*(4.5-3)=
=

输出样例 1

4.00
30.00

AC 代码

/*debug 近 4 个小时的血的教训：
1、不要使用 if (e) 和 if (!e) 这样花里胡哨的用法，
    或者说，现阶段为止，你必须用一次谨慎一次
2、不要迷信返回值，返回值不能给你过多的信息
3、需要理智去debug，比如这次里面，出现段错误，TLE和OLE，
    那么，很明显，这个是主函数出现错误
4、要自信
*/
#include <iostream>
#include <algorithm>

#define MAX 100

using namespace std;

typedef struct
{
    double *base;
    double *top;
    int maxSize;
}stack1;

void initStack1(stack1 &s)
{
    s.base = new double [MAX];
    if(!s.base)
        cout << "分配空间错误" << endl;
        
    s.top = s.base;
    s.maxSize = MAX;
}

void push1(stack1 &s, double e)
{
    if (s.top - s.base == s.maxSize)
        cout << "栈已满，无法添加" << endl;

    *s.top = e;
    s.top ++;
}

void pop1(stack1 &s)
{
    if (s.top == s.base)
        cout << "栈已空，无法删除" << endl;
        
    s.top --;
}

double top1(stack1 s)  
{
    if (s.top == s.base)
        cout << "栈已空，无法取值" << endl;

    return *(s.top - 1);
}

typedef struct
{
    char *base;
    char *top;
    int maxSize;
}stack2;

void initStack2(stack2 &s)
{
    s.base = new char [MAX];
    if (!s.base)
        cout << "分配空间错误" << endl;

    s.top = s.base;
    s.maxSize = MAX;
}

void push2(stack2 &s, char e)
{
    if (s.top - s.base == s.maxSize)
        cout << "栈已满，无法添加" << endl;

    *s.top = e;
    s.top ++;
}

void pop2(stack2 &s)
{
    if (s.top == s.base)
        cout << "栈已空，无法删除" << endl;        

    s.top --;
}

char top2(stack2 s)
{
    if (s.top == s.base)
        cout << "栈已空，无法取值" << endl;

    return *(s.top - 1);
}

char pre(char a,char b)                         // 记住表即可，深入理解
{
	if((a=='('&&b==')')||(a=='='&&b=='='))
		return '=';
	else if(a=='('||a=='='||b=='('||(a=='+'||a=='-')&&(b=='*'||b=='/'))
		return '<';
	else
		return '>';
}

double cal(double a, double b, char op)         // 注意 b 和 a应该反一下，因为栈的特性
{
    if (op == '+')
        return b + a;
    else if (op == '-')
        return b - a;
    else if (op == '*')
        return b * a;
    else 
        return b / a;
}

int main()
{
    string s;
    while (cin >> s && s[0] != '=')
    {
        stack1 ds;
        initStack1(ds);
        stack2 cs;
        initStack2(cs);
        
        push2(cs, '=');
        
        int x = 0, e = 0, flag = 0;
        /*基本思路：
        我们对于单个数字字符，先不进行push，而是等到下一个运算字符
        出现，我们通过判断来获得运算字符前面的几个数字字符构成的double类
        数字
        由于本题中每一次循环，都有可能有特例和上一次循环有联系
        因此，我们采用 flag 法，进行标记处理
        */
        for (int i = 0; s[i] != '\0'; i ++) 
        {
            if ('0' <= s[i] && s[i] <= '9')
            {
                flag = 1;
                x = x * 10 + (s[i] - '0');
                if (e != 0)
                    e *= 10;
            }
            else if (s[i] == '.')
                e = 1;
            else
            {
                if (flag != 0)
                {
                    double number = x;
                    if (e != 0)
                        number /= e;
                    push1(ds, number);
                    x = flag = e = 0;
                }
                while (1)
                {
                    if (pre(top2(cs), s[i]) == '<')
                    {
                        push2(cs, s[i]);
                        break;
                    }
                    else if (pre(top2(cs), s[i]) == '>')
                    {
                        double a = top1(ds);
                        pop1(ds);
                        double b = top1(ds);
                        pop1(ds);
                        
                        char op = top2(cs);
                        pop2(cs);
                        push1(ds, cal(a, b, op));
                    }
                    else
                    {
                        pop2(cs);
                        break;
                    }
                }
            }            
        }
        printf("%.2lf\n", top1(ds));
    }
    return 0;
}