用c++语言设计算法实现简单表达式求值

在C++中，我们可以使用栈（Stack）数据结构来设计一个简单的表达式求值算法。这里我们将使用递归前缀计算（Precedence-Driven Evaluation）方法，也称为逆波兰表示法（Reverse Polish Notation, RPN），因为在这种表示法下，运算符位于其操作数之后，适合使用栈来处理。

下面是实现的一个简单示例：

#include <stack>
#include <string>
#include <sstream>
#include <climits>

using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return INT_MAX; // 操作符优先级比所有数字都高
}

bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

double applyOp(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: assert(false); return 0; // 未处理的错误
    }
}

double evaluate(string tokens) {
    stack<double> values;
    stack<char> ops;

    for (char token : tokens) {
        if (isdigit(token)) {
            double num = 0;
            stringstream ss(token);
            ss >> num;
            values.push(num);
        } else if (isOperator(token)) {
            while (!ops.empty() && precedence(ops.top()) >= precedence(token)) {
                values.push(applyOp(values.top(), values.pop(), ops.top()));
                ops.pop();
            }
            ops.push(token);
        } else {
            assert(false && "Invalid token");
        }
    }

    while (!ops.empty()) {
        values.push(applyOp(values.top(), values.pop(), ops.top()));
        ops.pop();
    }

    return values.top();
}

int main() {
    string expression = "2 3 + 4 *";
    cout << "Result of expression: " << evaluate(expression) << endl;
    return 0;
}

在这个例子中，我们遍历输入的字符串`tokens`，如果是数字就压入数值栈`values`，如果是运算符则比较其优先级，将低优先级的运算符应用到栈顶两个操作数上。最后，处理完所有的运算符后，剩下的就是最终结果。