能否提供一个将中缀表达式转换为后缀(逆波兰)形式,并用C++实现的示例代码?
时间: 2024-10-21 09:14:57 浏览: 78
当然可以。中缀表达式转后缀(逆波兰)也叫前缀表达式,是一个常见的算法练习,涉及到递归栈操作。下面是一个简单的C++函数,使用了栈来完成这个任务:
```cpp
#include <iostream>
#include <stack>
#include <string>
std::string infixToPostfix(const std::string& infix) {
std::stack<char> opStack;
std::string postfix = "";
char precedence[6] = {'(', ')', '*', '/', '+'};
int i = 0;
while (i < infix.length()) {
if (isdigit(infix[i])) { //数字直接添加到后缀
postfix += infix[i];
i++;
} else if (infix[i] == ' ') { //跳过空格
i++;
} else if (infix[i] == '(') { //左括号压入栈
opStack.push(infix[i]);
} else if (infix[i] == ')') { //右括号,弹出并加到后缀直到遇到左括号
while (!opStack.empty() && opStack.top() != '(') {
postfix += opStack.top();
opStack.pop();
}
if (!opStack.empty()) {
opStack.pop(); //移除左括号
}
} else { //运算符,比较优先级并处理
while (!opStack.empty() && precedence[opStack.top()] >= precedence[infix[i]]) {
postfix += opStack.top();
opStack.pop();
}
opStack.push(infix[i]); //运算符推到栈顶
}
}
//处理剩下的运算符
while (!opStack.empty()) {
postfix += opStack.top();
opStack.pop();
}
return postfix;
}
int main() {
std::string expression = "A+B*C/(D-E)";
std::cout << "Infix to Postfix conversion: " << infixToPostfix(expression) << std::endl;
return 0;
}
```
在这个例子中,我们遍历输入的中缀表达式,遇到数字、空格、括号或运算符时分别进行相应处理。注意,这只是一个基础版本,实际应用中可能需要考虑更多细节,比如处理括号嵌套的情况。
阅读全文