前缀表达式（波兰表达式）

前缀表达式的运算符位于操作数之前，不需要括号来定义运算顺序，运算顺序完全由运算符的位置决定。例如，+ 3 4 等价于中缀表达式的 3 + 4。

• 示例：

  • + * 3 4 5 等价于中缀的 (3 * 4) + 5。
  • - + 1 2 * 3 4 等价于中缀的 (1 + 2) - (3 * 4)。

• 计算方法： 从右向左扫描表达式，遇到操作数压栈，遇到运算符弹出栈顶两个操作数计算，并将结果压栈。

#include <stack>
#include <string>
#include <sstream>
using namespace std;

int evaluatePrefix(const string& expr) {
    stack<int> st;
    istringstream iss(expr);
    string token;
    while (iss >> token) {
        if (isdigit(token[0])) {
            st.push(stoi(token));
        } else {
            int a = st.top(); st.pop();
            int b = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else if (token == "/") st.push(a / b);
        }
    }
    return st.top();
}

中缀表达式

中缀表达式是常见的数学表达式形式，运算符位于操作数之间，例如 3 + 4 * 5。中缀表达式需要括号或优先级规则来明确运算顺序。

• 示例：

  • 3 + 4 * 5 的运算顺序是 3 + (4 * 5)。
  • (3 + 4) * 5 的运算顺序是 (3 + 4) * 5。

• 计算方法： 通常需要转换为前缀或后缀表达式后再计算，或使用双栈法（操作数栈和运算符栈）直接求值。

#include <stack>
#include <string>
#include <cctype>
using namespace std;

int evaluateInfix(const string& expr) {
    stack<int> nums;
    stack<char> ops;
    for (int i = 0; i < expr.size(); ++i) {
        if (expr[i] == ' ') continue;
        if (isdigit(expr[i])) {
            int num = 0;
            while (i < expr.size() && isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                ++i;
            }
            --i;
            nums.push(num);
        } else if (expr[i] == '(') {
            ops.push(expr[i]);
        } else if (expr[i] == ')') {
            while (ops.top() != '(') {
                char op = ops.top(); ops.pop();
                int b = nums.top(); nums.pop();
                int a = nums.top(); nums.pop();
                if (op == '+') nums.push(a + b);
                else if (op == '-') nums.push(a - b);
                else if (op == '*') nums.push(a * b);
                else if (op == '/') nums.push(a / b);
            }
            ops.pop();
        } else {
            while (!ops.empty() && ops.top() != '(' && 
                   ((expr[i] == '+' || expr[i] == '-') && 
                    (ops.top() == '*' || ops.top() == '/'))) {
                char op = ops.top(); ops.pop();
                int b = nums.top(); nums.pop();
                int a = nums.top(); nums.pop();
                if (op == '+') nums.push(a + b);
                else if (op == '-') nums.push(a - b);
                else if (op == '*') nums.push(a * b);
                else if (op == '/') nums.push(a / b);
            }
            ops.push(expr[i]);
        }
    }
    while (!ops.empty()) {
        char op = ops.top(); ops.pop();
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        if (op == '+') nums.push(a + b);
        else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b);
        else if (op == '/') nums.push(a / b);
    }
    return nums.top();
}

后缀表达式（逆波兰表达式）

后缀表达式的运算符位于操作数之后，例如 3 4 + 等价于中缀的 3 + 4。后缀表达式无需括号，运算顺序由运算符位置决定。

• 示例：

  • 3 4 * 5 + 等价于中缀的 (3 * 4) + 5。
  • 1 2 + 3 4 * - 等价于中缀的 (1 + 2) - (3 * 4)。

• 计算方法： 从左向右扫描表达式，遇到操作数压栈，遇到运算符弹出栈顶两个操作数计算，并将结果压栈。

#include <stack>
#include <string>
#include <sstream>
using namespace std;

int evaluatePostfix(const string& expr) {
    stack<int> st;
    istringstream iss(expr);
    string token;
    while (iss >> token) {
        if (isdigit(token[0])) {
            st.push(stoi(token));
        } else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else if (token == "/") st.push(a / b);
        }
    }
    return st.top();
}

转换方法

中缀表达式可以转换为前缀或后缀表达式，常用方法包括：

• 中缀转后缀：使用栈处理运算符优先级，输出操作数并调整运算符顺序。
• 中缀转前缀：从右向左扫描中缀表达式，使用栈处理运算符优先级。

转换算法的核心是通过栈管理运算符优先级和括号匹配。