数据结构3.3表达式求值

 表达式求值有很多巧妙之处，临摹自刘知鑫

先看代码

#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
stack num;
stack 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 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;
}

此处掉了很多库

#include ：用于存储iostream类库的 源文件 ，在这个程序中用于提供输出这项功能。
#include ：函数的头文件之下包含有很多实用的字符串函数
#include ：定义了一组专门设计用于元素范围的函数集合
#include ：使用特定容器类的封装对象作为其基础容器的类，提供了一组特定的成员函数来访问其元素。 元素从特定容器的“后面”被推入/弹出，这被称为堆栈的顶部。
#include ：无需存储容器， unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。

精巧之处便是：定义了两个栈，一个存储数字，一组存储运算符，对于压栈、弹栈、循环条件的判断极其精巧。

、