表达式求值

本题也算一个很经典的栈的应用了

思路分析

计算中缀表达式，需要用到两个栈，一个栈存储数字，另一个存储运算符

其次如何计算？

1.读入数字则存储

可以通过自带的$isdigit()$函数判断一个字符是否是数字，也可以通过$ASCII$码自己实现函数判断
因为字符串是一个整体，所以我们采用一个双指针维护一段区间，j指向数字

    int x = 0, j = i;
    while (j < str.size() && isdigit(str[j]))
        x = x * 10 + str[j ++ ] - '0';
    i = j - 1;

j最后指的是数字后面第一个运算符，因为每一轮 $i ++ $， 所以$j = i - 1$

2.读入字符，则优先级判断

栈顶运算符，和即将入栈的运算符的优先级比较：

如果栈顶的运算符优先级低，新运算符直接入栈

如果栈顶的运算符优先级高(或者相等)，先出栈计算，新运算符再入栈

括号是优先级最高的，遇到左括号，入栈，遇到右括号，就一直计算直到遇到左括号

优先级存储问题

写判断函数比较麻烦，于是，我们采用哈希表来映射字符与优先级的关系，数字越大优先级越高，数字相等，在前面的优先级高(这是易于理解的，$1 + 2 + 3$，先算$1 + 2$， $1 + 2 * 3$， 先算 $2 * 3$)

unordered_map<char, int> h{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;//数字栈
stack<char> op;//字符栈

void eval()
{
    auto b = num.top(); num.pop(); // 取出第二个操作数
    auto a = num.top(); num.pop(); // 取出第一个操作数
    auto c = op.top(); op.pop();  // 取出操作符
    int x;  //进行运算
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);  //运算结果入栈
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};  //优先级映射表
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))  //读入数字
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);  //左括号直接入栈
        else if (c == ')')  //有括号，一直运算，直到碰到左括号
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else  // 若栈顶优先级大于等于当前运算符，则运算，运算完后运算符入栈
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();  //若还有运算符没计算，则持续计算
    cout << num.top() << endl;  //输出栈顶元素
    return 0;
}