用C++写一个用栈实现的逆波兰表达式

在C++中，我们可以使用栈数据结构来实现逆波兰（RPN，Reverse Polish Notation）表达式的计算。逆波兰表达式是一种不需要括号就能明确表达运算顺序的表示法。下面是一个简单的示例，展示了如何使用栈来解析和求值逆波兰表达式：

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

// 定义操作数的数据类型
typedef int Operand;

// 操作符优先级
const int PRIORITY[] = {0, // 空格和数字
                        1, // 函数如sqrt()
                        2, // 开方、指数等
                        3, // 乘除
                        4, // 加减};

// 用于比较操作符优先级的函数
int comparePriority(char op1, char op2) {
    return PRIORITY[op1] - PRIORITY[op2];
}

// 栈中元素的结构体
struct Item {
    char op;   // 操作符
    Operand num; // 数字
};

// 将操作数压入栈
void pushOperand(stack<Item>& s, const string& token) {
    if (isdigit(token[0])) {
        s.push({'.', stoi(token)});
    } else {
        s.push({token[0], 0});
    }
}

// 解析并处理表达式
double evalRPN(const stack<Item>& s) {
    double result = 0;
    while (!s.empty()) {
        Item item = s.top();
        s.pop();

        switch (item.op) {
            case '+':
                result += item.num;
                break;
            case '-':
                result -= item.num;
                break;
            case '*':
                result *= item.num;
                break;
            case '/':
                result /= item.num;
                break;
            default: // 如果遇到非运算符，直接返回结果
                return result;
        }
    }
    return result;
}

int main() {
    string rpnExpr = "2 3 + 4 *"; // 示例逆波兰表达式
    stack<Item> exprStack;
    size_t i = 0;

    // 分割表达式到单词
    while (i < rpnExpr.length()) {
        char c = rpnExpr[i];
        if (c == ' ') {
            continue;
        } else if (isdigit(c)) {
            pushOperand(exprStack, rpnExpr.substr(i));
        } else {
            Item opItem = exprStack.top();
            exprStack.pop(); // 弹出当前操作符

            while (!exprStack.empty() && comparePriority(opItem.op, exprStack.top().op) >= 0) {
                Item oprItem = exprStack.top();
                exprStack.pop();
                opItem.num = evalRPN(exprStack);
                opItem.op = oprItem.op;
            }
            exprStack.push(opItem); // 将操作符推回栈
        }
        i++;
    }

    // 计算最终结果
    cout << "Result: " << evalRPN(exprStack) << endl;

    return 0;
}

这个程序首先将输入的逆波兰表达式分割成单词（数字或操作符），然后遍历每个词，处理加减乘除等运算。当遇到一个操作符时，它会检查栈顶的操作符是否比当前操作符优先级高，如果低则将其弹出，直到找到可以匹配的较高优先级的操作符，然后执行相应的运算。