中缀表达式转后缀表达式
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;
转换过程分析：
- 读取
2：数字，直接加入结果，添加#→2# - 读取
^：运算符，栈为空，直接入栈 → 栈:^ - 读取
3：数字，加入结果，添加#→2#3# - 读取
!：运算符，栈顶是^(优先级3)，!优先级4更高，直接入栈 → 栈:^, ! - 表达式结束，弹出所有运算符 →
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'&¤tChar<='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;
}