中缀表达式求值（栈的应用）-Toy模板网

这篇具有很好参考价值的文章主要介绍了中缀表达式求值（栈的应用）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目来源

AcWing算法基础课-3302.表达式求值

二、题目描述

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

注意：

数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-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)

输出样例：

三、算法思路

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

思路如下：

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

注意事项：文章来源地址https://www.toymoban.com/news/detail-747292.html

遇到数字要 \(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;
}

到了这里，关于中缀表达式求值（栈的应用）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！