中缀表达式求值（栈的应用）

一、题目来源

二、题目描述

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 \(2 ^ {31} - 1\)。
• 题目中的整除是指向 \(0\) 取整，也就是说对于大于 \(0\) 的结果向下取整，例如 \(5/3=1\)，对于小于 \(0\) 的结果向上取整，例如 \(5/(1−4)=−1\)。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 \(10^5\)。

输入样例：

(2+2)*(1+1) 

输出样例：

8 

三、算法思路

本题是中缀表达式求值问题，主要为栈的应用。

思路如下：

• 首先，设置两个栈，一个为操作符栈，一个为数字栈。
• 然后，遍历整个序列：
  • 遇到 '(' ，直接 \(push\)
  • 遇到数字，直接 \(push\)
  • 遇到操作符
    • 如果是 '+'、‘-’，那么都可以算
      • \(while\) 栈不空 且 栈顶不是'('
        • 操作
    • 如果是 '*'、'/'，那么加减不能先算，只能算乘除
      • \(while\) 栈不空 且 栈顶是 '*'、'/'
        • 操作
    • 最后 \(push\)
  • 遇到 ')'
    • \(while\) 栈顶不是 '('
      • 操作
    • 将 '(' 弹出
• 处理 操作符栈中 剩余的操作符
• 数字栈的栈顶为最终答案

注意事项：

• 遇到数字要 \(push\)，但是数字可能不是个位数，显然有可能是多位数（但不会是负数），所以需要处理一下。
• 可以将判断是否是数字、加减、乘除、操作这些抽象成函数，这样代码好写一些。
• 一定要注意，加减的运算级比乘除低，所以遇到加减可以算之前的乘除，而遇到乘除不能先算之前的加减，例如 \(2+3*5\)，如果搞错了就会得出 \(25\)，读者自行思考。
• 遍历完之后别忘了将剩余的操作符都要处理掉。

四、源代码

#include <iostream>

using namespace std;

const int N = 100010;

char op[N];
int num[N];
int opt, numt;

void init()
{
    opt = 0;
    numt = 0;
}

bool isDigit(char c)
{
    if (c >= '0' && c <= '9')   return true;
    return false;
}

bool isAddOrSub(char c)
{
    if (c == '+' || c == '-')   return true;
    return false;
}

bool isMulOrDiv(char c)
{
    if (c == '*' || c == '/')   return true;
    return false;
}

void func()
{
    char c = op[-- opt];
    int num1 = num[-- numt], num2 = num[-- numt];
    
    int res = 0;
    if (c == '+')   res = num2 + num1;
    else if (c == '-')  res = num2 - num1;
    else if (c == '*')  res = num2 * num1;
    else    res = num2 / num1;
    
    num[numt ++ ] = res;
}

int main()
{
    string s;
    cin >> s;
    
    init();
    
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == '(')    op[opt ++ ] = s[i];
        else if (isDigit(s[i]))
        {
            int res = 0, j = i;
            while (j < s.size() && isDigit(s[j]))
                res = res * 10 + s[j ++ ] - '0';
                
            num[numt ++ ] = res;
            
            i = j - 1;
        }
        else if (isAddOrSub(s[i]) || isMulOrDiv(s[i]))
        {
            if (isAddOrSub(s[i]))
                while (opt != 0 && op[opt - 1] != '(')
                    func();
            else
                while (opt != 0 && isMulOrDiv(op[opt - 1]))
                    func();
        
            op[opt ++ ] = s[i];
        }
        else
        {
            while (op[opt - 1] != '(')  func();
            opt -- ;
        }
    }
    
    while (opt != 0)    func();
    
    cout << num[numt - 1] << endl;
    
    return 0;
}