基于堆栈的中缀表达式转换算法实现 (C++)

介绍如何利用 C++ 的堆栈数据结构实现中缀表达式到其他表达式的转换。

算法原理

中缀表达式转换为其他表达式（例如后缀表达式）的核心思想是利用堆栈对运算符进行优先级排序和暂存。

1. 初始化: 创建一个空堆栈用于存储运算符，并准备一个输出队列或字符串用于存储转换后的表达式。
2. 遍历表达式: 从左到右依次读取中缀表达式中的每个字符。
   • 如果遇到操作数，则直接将其添加到输出队列或字符串中。
   • 如果遇到运算符，则将其与堆栈顶部的运算符进行优先级比较：
     • 如果堆栈为空或当前运算符的优先级高于堆栈顶部运算符，则将当前运算符压入堆栈。
     • 如果当前运算符的优先级低于或等于堆栈顶部运算符，则将堆栈顶部运算符弹出并添加到输出队列或字符串中，直到当前运算符可以压入堆栈为止。
   • 如果遇到左括号，则直接将其压入堆栈。
   • 如果遇到右括号，则将堆栈中的运算符依次弹出并添加到输出队列或字符串中，直到遇到左括号为止（左括号弹出但不添加到输出中）。
3. 处理剩余运算符: 当表达式遍历完成后，将堆栈中剩余的运算符依次弹出并添加到输出队列或字符串中。

代码实现

#include 
#include 
#include 

using namespace std;

// 判断运算符优先级
int precedence(char op) {
  if (op == '+' || op == '-') {
    return 1;
  } else if (op == '*' || op == '/') {
    return 2;
  }
  return 0; 
}

// 中缀表达式转后缀表达式
string infixToPostfix(const string& infix) {
  stack opStack;
  string postfix = "";

  for (char c : infix) {
    if (isalnum(c)) {  // 操作数直接输出
      postfix += c;
    } else if (c == '(') {
      opStack.push(c);
    } else if (c == ')') {
      while (!opStack.empty() && opStack.top() != '(') {
        postfix += opStack.top();
        opStack.pop();
      }
      opStack.pop();  // 弹出 '('
    } else {  // 运算符
      while (!opStack.empty() && precedence(c) <= precedence(opStack.top())) {
        postfix += opStack.top();
        opStack.pop();
      }
      opStack.push(c);
    }
  }

  while (!opStack.empty()) {
    postfix += opStack.top();
    opStack.pop();
  }

  return postfix;
}

int main() {
  string infix = "a+b*c-(d+e)";
  string postfix = infixToPostfix(infix);
  cout << "Infix expression: " << infix>

总结

介绍了基于堆栈的中缀表达式转换算法的原理和 C++ 实现。该算法可以有效地将中缀表达式转换为其他形式的表达式，为后续的表达式求值等操作奠定了基础。