算术表达式求值数据结构c++

常用的算术表达式求值数据结构是栈。具体实现步骤如下：

1. 定义一个栈，用于存储数字和操作符；
2. 遍历表达式中的每个字符，如果是数字则直接入栈，如果是操作符则弹出栈顶的两个数字进行运算，将结果再次入栈；
3. 最终栈中只剩下一个数字，即为表达式的求值结果。

以下是一个简单的 C++ 实现：

#include <iostream>
#include <stack>
using namespace std;

int evaluateExpression(string exp) {
    stack<int> s;
    for (int i = 0; i < exp.length(); i++) {
        if (isdigit(exp[i])) {
            int num = 0;
            while (i < exp.length() && isdigit(exp[i])) {
                num = num * 10 + exp[i] - '0';
                i++;
            }
            i--;
            s.push(num);
        } else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
            int num1 = s.top();
            s.pop();
            int num2 = s.top();
            s.pop();
            switch (exp[i]) {
                case '+':
                    s.push(num2 + num1);
                    break;
                case '-':
                    s.push(num2 - num1);
                    break;
                case '*':
                    s.push(num2 * num1);
                    break;
                case '/':
                    s.push(num2 / num1);
                    break;
            }
        }
    }
    return s.top();
}

int main() {
    string exp = "3+4*2-1";
    int result = evaluateExpression(exp);
    cout << "The result of " << exp << " is " << result << endl;
    return 0;
}

输出结果为：

The result of 3+4*2-1 is 10