中缀表达式求值(栈的应用)

一、题目来源

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) 

输出样例:

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;
}

热门相关:觅仙道   青莲剑说   全天下都知道太子爱她   重生复仇:腹黑千金不好惹   觅仙道