基于调度场算法将中缀表达式转换为后缀表达式

中缀表达式转后缀表达式

1. 整体结构概述

这段C++代码实现了一个中缀表达式转后缀表达式（逆波兰表达式）的转换器。主要包含：

• 一个InfixToPostfixConverter类，负责转换逻辑
• main函数作为程序入口，进行简单测试

转换支持的运算符包括：!(阶乘)、^(幂运算)、*(乘法)、/(除法)、+(加法)、-(减法)，以及括号()改变运算优先级。

2. 类成员与数据结构

私有成员

char opStack[MAXSIZE];  // 运算符栈
int opTop;              // 栈顶指针

• 使用固定大小数组实现栈结构，MAXSIZE定义为100
• opTop初始值为-1，表示空栈

优先级判断函数

int getOperatorPriority(char op) const {switch (op) {case '!': return 4;case '^': return 3;case '*': case '/': return 2;case '+': case '-': return 1;case '(': return 0;default: return -1;}
}

优先级从高到低为：! > ^ > *// > +/-，左括号(优先级最低。

3. 转换核心算法：convertToPostfix方法

该方法接收一个中缀表达式字符串，返回对应的后缀表达式。算法流程如下：

3.1 初始化

string postfixExpr;  // 存储结果的后缀表达式
int exprLen = infixExpr.length();  // 输入表达式长度

3.2 遍历表达式

对中缀表达式的每个字符进行处理：

3.2.1 处理左括号(

if (currentChar == '(') {if (opTop < MAXSIZE - 1) {opStack[++opTop] = currentChar;}continue;
}

• 直接将左括号压入运算符栈

3.2.2 处理右括号)

if (currentChar == ')') {while (opTop != -1 && opStack[opTop] != '(') {postfixExpr += opStack[opTop--];  // 弹出运算符到结果}opTop--;  // 弹出左括号但不加入结果continue;
}

• 弹出栈中所有运算符直到遇到左括号
• 左括号只弹出不加入结果

3.2.3 处理运算符

if (currentChar是运算符) {while(opTop!=-1){char topOp=opStack[opTop];// 栈顶运算符优先级高于等于当前运算符时弹出if(getOperatorPriority(topOp)>=getOperatorPriority(currentChar)){postfixExpr+=topOp;opTop--;}else{break;}}// 当前运算符入栈if(opTop<MAXSIZE-1){opStack[++opTop]=currentChar;}continue;
}

• 遵循"栈顶运算符优先级高于等于当前运算符则弹出"的规则
• 最后将当前运算符压入栈

3.2.4 处理数字

if(currentChar是数字){while(i<exprLen&&infixExpr[i]是数字){postfixExpr+=infixExpr[i];  // 收集连续数字++i;}postfixExpr+='#';  // 用#标记数字结束--i;  // 调整循环变量continue;
}

• 收集连续数字字符作为一个完整数字
• 用#作为数字结束标记，方便后续计算时解析

3.3 处理剩余运算符

while(opTop!=-1){postfixExpr+=opStack[opTop--];  // 弹出所有剩余运算符
}

• 遍历结束后，将栈中剩余运算符全部弹出到结果

4. 测试示例分析

main函数测试了表达式"2^3!"的转换：

cout<<infix.convertToPostfix("2^3!")<<endl;

转换过程分析：

1. 读取2：数字，直接加入结果，添加# → 2#
2. 读取^：运算符，栈为空，直接入栈 → 栈: ^
3. 读取3：数字，加入结果，添加# → 2#3#
4. 读取!：运算符，栈顶是^(优先级3)，!优先级4更高，直接入栈 → 栈: ^, !
5. 表达式结束，弹出所有运算符 → 2#3#!^

所以最终输出为：2#3#!^

5. 算法流程图

开始|
初始化栈和结果字符串|
遍历中缀表达式的每个字符|
├─ 若为'(' → 入栈
│
├─ 若为')' → 弹出运算符直到'('，弹出'('不加入结果
│
├─ 若为运算符 → 弹出栈中优先级>=当前运算符的运算符，当前运算符入栈
│
└─ 若为数字 → 收集连续数字，添加#标记|
遍历结束后，弹出栈中所有运算符到结果|
返回后缀表达式|
结束

该实现通过栈数据结构实现了中缀到后缀表达式的转换，核心在于运算符优先级的比较和栈操作规则。代码使用#作为数字分隔符，便于后续对后缀表达式进行计算。对于测试用例2^3!，按照运算符优先级规则，正确转换为2#3#!^。
附上完整代码：

#include <iostream>
using namespace std;
const int MAXSIZE = 100;
class InfixToPostfixConverter {private:char opStack[MAXSIZE];int opTop;// 获取优先级int getOperatorPriority(char op) const {switch (op) {case '!':return 4;case '^':return 3;case '*':case '/':return 2;case '+':case '-':return 1;case '(':return 0;default:return -1;}}public:InfixToPostfixConverter() : opTop(-1) {}string convertToPostfix(const string& infixExpr) {string postfixExpr;int exprLen = infixExpr.length();for (int i = 0; i < exprLen; ++i) {char currentChar = infixExpr[i];// 左括号if (currentChar == '(') {if (opTop < MAXSIZE - 1) {opStack[++opTop] = currentChar;}continue;}// 右括号if (currentChar == ')') {while (opTop != -1 && opStack[opTop] != '(') {postfixExpr += opStack[opTop--];}// 弹出左括号opTop--;continue;}// 处理运算符if (currentChar == '+' || currentChar == '-' ||currentChar == '*' || currentChar == '/' ||currentChar == '^' || currentChar == '!') {//假定是否一直出栈while(opTop!=-1){char topOp=opStack[opTop];if(getOperatorPriority(topOp)>=getOperatorPriority(currentChar)){postfixExpr+=topOp;opTop--;}else{break;}}if(opTop<MAXSIZE-1){opStack[++opTop]=currentChar;}continue;}if(currentChar>='0'&&currentChar<='9'){while(i<exprLen&&infixExpr[i]>='0'&&infixExpr[i]<='9'){postfixExpr+=infixExpr[i];++i;}postfixExpr+='#';--i;continue;}}//所有的表达式的运算符都已经入栈后，运算符栈内仍然有剩余的运算符，弹出所有剩余的运算符while(opTop!=-1){postfixExpr+=opStack[opTop--];}return postfixExpr;}
};
int main() {InfixToPostfixConverter infix;cout<<infix.convertToPostfix("2^3!")<<endl;return 0;
}