| 表达式 | 定义 | 示例 |
|---|---|---|
| 前缀表达式 | 运算符位于操作数之前 | - × + 3 4 5 6 |
| 中缀表达式 | 操作符以中缀形式处于操作数的中间 | (3 + 4) × 5 - 6 |
| 后缀表达式 | 运算符位于操作数之后 | 3 4 + 5 × 6 - |
前缀式，后缀式是不需要用括号来进行优先级的确定的。
遵循以下步骤：
-+1*+2345
思路： 递归，碰到操作符就进入递归。
与转换为前缀表达式相似，遵循以下步骤：
1 2 3 + 4* 5 - +
基本思路和上面的一样： 递归，碰到操作符就进入递归
// 判断是否为括号
bool isPra(char c) {
return (c == '(' || c == ')') ? true : false;
}
// 获得符号的优先性
int getPri(char c)
{
switch (c) {
case '+':
case '-':
return 0; // 如果是加减，返回0
break;
case '*':
case '/':
return 1; // 如果是乘除，返回1
break;
case '(':
case ')':
return -1; // 这里将括号设为最低优先级，因此括号不会被弹出，除非遇到右括号
break;
default:
cout << "输入其他运算符\n" << endl;
}
}
//判断符号的优先性
void check(char c, stack<char>& operator_s, string& suffix) {
if (operator_s.empty()) {
operator_s.push(c);
return;
}
if (isPra(c)) {
if (c == '(') {
operator_s.push(c);
}
else {
// 弹出所有元素直到遇到左括号
while (operator_s.top() != '(') {
suffix += operator_s.top();
operator_s.pop();
}
// 遇到左括号，弹出且不加入后缀表达式
operator_s.pop();
}
}
else {
// 如果不是括号，比较当前元素，与栈顶元素的优先级
if (getPri(c) > getPri(operator_s.top())) {
operator_s.push(c);
}
else {
suffix += operator_s.top();
operator_s.pop();
// 递归调用，比较当前符号c与下一个栈顶符号的优先性
check(c, operator_s, suffix);
}
}
}
// 中缀表达式转后缀表达式
string infixToSuffix(string& infix) {
stack<char> operator_s; // 运算符栈
string suffix; // 后缀表达式
//int num = 0;
for (int i = 0; i < infix.size(); ++i) {
if (infix[i] >= '0' && infix[i] <= '9') {
suffix += infix[i];
}
else {
check(infix[i], operator_s, suffix);
}
}
// 对中缀表达式的遍历结束，将栈中元素加入后缀表达式
while (!operator_s.empty()) {
suffix += operator_s.top();
operator_s.pop();
}
return suffix;
}
这里给出中缀表达式：a+b*c-(d+e)
按照运算符的优先级对所有的运算单位加括号~
式子变成：((a+(b* c))-(d+e))
转换成前缀表达式与后缀表达式
首先确定表达式表达式A的运算顺序，然后加括号：（（1 + (( 2 + 3)* 4 )） – 5 ）
从最里面的一层括号开始运算，转换成前缀表达式的方法为：（忽略括号）符号在前，数字在后。
演示过程如下：
前缀表达式为：-+1*+2345
首先确定表达式表达式A的运算顺序，然后加括号：（（1 + (( 2 + 3)* 4 )） – 5 ）
从最里面的一层括号开始运算，转换成后缀表达式的方法为：（忽略括号）数字在前，符号在后。
演示过程如下：
后缀表达式为：123 + 4*+ 5 –