C++中缀式转后缀式代码
时间: 2023-12-05 22:04:46 浏览: 40
下面是 C++ 实现中缀表达式转后缀表达式的代码,使用了栈来存储运算符:
```cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// 判断是否是运算符
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
// 判断运算符优先级
int getPriority(char op) {
if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else if (op == '^')
return 3;
else
return 0;
}
// 中缀表达式转后缀表达式
string infixToPostfix(string infix) {
stack<char> s;
string postfix;
for (char c : infix) {
if (isalnum(c)) {
postfix += c;
}
else if (c == '(') {
s.push(c);
}
else if (c == ')') {
while (!s.empty() && s.top() != '(') {
postfix += s.top();
s.pop();
}
s.pop(); // 弹出左括号
}
else if (isOperator(c)) {
while (!s.empty() && getPriority(s.top()) >= getPriority(c)) {
postfix += s.top();
s.pop();
}
s.push(c);
}
}
while (!s.empty()) {
postfix += s.top();
s.pop();
}
return postfix;
}
int main() {
string infix = "a+b*c-(d/e+f)*g";
string postfix = infixToPostfix(infix);
cout << postfix << endl; // 输出 abc*+de/f+g*-
return 0;
}
```
代码中,`isOperator` 函数用于判断字符是否为运算符,`getPriority` 函数返回运算符的优先级。`infixToPostfix` 函数从左至右遍历中缀表达式,对于每个字符进行如下操作:
- 如果是字母或数字,直接加入后缀表达式;
- 如果是左括号,入栈;
- 如果是右括号,弹出栈顶元素直到遇到左括号,弹出左括号;
- 如果是运算符,弹出栈中优先级不低于当前运算符的元素,直到遇到优先级更低的元素或栈为空,将当前运算符入栈;
- 最后,将栈中所有元素依次加入后缀表达式即可。
例如,对于中缀表达式 `a+b*c-(d/e+f)*g`,运行 `infixToPostfix` 函数后得到的后缀表达式为 `abc*+de/f+g*-`。