将中缀转换为后缀表达式
前缀表达式是人类可读和可解的。我们可以轻松地区分算子的顺序，也可以在计算数学表达式时先使用括号将其求解。计算机无法轻松地区分运算符和括号，这就是为什么需要后缀转换的原因。
要将中缀表达式转换为后缀表达式，我们将使用堆栈数据结构。通过从左到右扫描infix表达式，当我们得到任何操作数时，只需将它们添加到后缀形式中，并为运算符和括号将它们添加到堆栈中以保持它们的优先级。
注意：这里我们将仅考虑{+，-，*，/，^}运算符，而忽略其他运算符。
输入输出
Input: The infix expression. x^y/(5*z)+2 Output: Postfix Form Is: xy^5z*/2+
算法
infixToPostfix(infix)
输入-中缀表达式。
输出-将中缀表达式转换为后缀形式。
Begin
initially push some special character say # into the stack
for each character ch from infix expression, do
if ch is alphanumeric character, then
add ch to postfix expression
else if ch = opening parenthesis (, then
push ( into stack
else if ch = ^, then //exponential operator of higher precedence
push ^ into the stack
else if ch = closing parenthesis ), then
while stack is not empty and stack top ≠ (,
do pop and add item from stack to postfix expression
done
pop ( also from the stack
else
while stack is not empty AND precedence of ch <= precedence of stack top element, do
pop and add into postfix expression
done
push the newly coming character.
done
while the stack contains some remaining characters, do
pop and add to the postfix expression
done
return postfix
End示例
#include<iostream>
#include<stack>
#include<locale> //for function isalnum()using namespace std;
int preced(char ch) {
if(ch == '+' || ch == '-') {
return 1; //Precedence of + or - is 1
}else if(ch == '*' || ch == '/') {
return 2; //Precedence of * or / is 2
}else if(ch == '^') {
return 3; //Precedence of ^ is 3
}else {
return 0;
}
}
string inToPost(string infix ) {
stack<char> stk;
stk.push('#'); //add some extra character to avoid underflow
string postfix = ""; //initially the postfix string is empty
string::iterator it;
for(it = infix.begin(); it!=infix.end(); it++) {
if(isalnum(char(*it)))
postfix += *it; //add to postfix when character is letter or number
else if(*it == '(')
stk.push('(');
else if(*it == '^')
stk.push('^');
else if(*it == ')') {
while(stk.top() != '#' && stk.top() != '(') {
postfix += stk.top(); //store and pop until ( has found
stk.pop();
}
stk.pop(); //remove the '(' from stack
}else {
if(preced(*it) > preced(stk.top()))
stk.push(*it); //push if precedence is high
else {
while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
postfix += stk.top(); //store and pop until higher precedence is found
stk.pop();
}
stk.push(*it);
}
}
}
while(stk.top() != '#') {
postfix += stk.top(); //store and pop until stack is not empty.
stk.pop();
}
return postfix;
}
int main() {
string infix = "x^y/(5*z)+2";
cout << "Postfix Form Is: " << inToPost(infix) << endl;
}输出结果
Postfix Form Is: xy^5z*/2+