STL模板之栈stack实例：中缀表达式转

后缀表达式

#include <iostream>
#include <stack>
#include <string>

using namespace std;

// 判断是否为数字
bool is_digit(char c) {
return c >= '0' && c <= '9';
}

// 判断是否为操作符
bool is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取操作符的优先级
int get_priority(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
} else {
return 0;
}
}

// 将中缀表达式转换为后缀表达式
string infix_to_postfix(string infix) {
string postfix; // 后缀表达式
stack<char> op_stack; // 操作符栈

// 遍历中缀表达式
for (int i = 0; i < infix.size(); i++) {
char c = infix[i];
if (is_digit(c)) { // 如果是数字，直接加入后缀表达式
postfix += c;
} else if (c == '(') { // 如果是左括号，入栈
op_stack.push(c);
} else if (c == ')') { // 如果是右括号，弹出栈中操作符直到遇到左括号
while (!op_stack.empty() && op_stack.top() != '(') {
postfix += op_stack.top();
op_stack.pop();
}
if (!op_stack.empty()) {
op_stack.pop(); // 弹出左括号
}
} else if (is_operator(c)) { // 如果是操作符
// 弹出栈中优先级高于等于当前操作符的操作符
while (!op_stack.empty() && get_priority(op_stack.top()) >= get_priority(c)) {
postfix += op_stack.top();
op_stack.pop();
}
op_stack.push(c); // 当前操作符入栈
}
}

// 弹出栈中剩余的操作符
while (!op_stack.empty()) {
postfix += op_stack.top();
op_stack.pop();
}

return postfix;
}

int main() {
string infix = "3+(4*5/(6-7))";
string postfix = infix_to_postfix(infix);
cout << postfix << endl; // 345*67-/+
return 0;
}