c++堆栈的应用：中缀表达式转化为后缀表达式
1、首先假设我们需要转化的中缀表达式为：
a + b * c + ( d * e + f ) * g
正确转化结果应为：
a b c * + d e * f + g * +
（字母代表一种操作数，+、*为操作符）
下面介绍一下基于堆栈的算法。堆栈用于存储操作符。
2、从左到右扫描每一个字符。如果扫描到的字符是操作数（如a、b等），就直接输出这些操作数。
3、如果扫描到的字符是一个操作符，分三种情况：
（1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）
（2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）
（3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。
4、如果遇到的操作符是左括号"（”，就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。
5、如果扫描到的操作符是右括号“）”，将堆栈中的操作符导出（pop）到output中输出，直到遇见左括号“（”。将堆栈中的左括号移出堆栈（pop ）。继续扫描下一个字符
6、如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。
7、以上是中缀表达式转化为后缀表达式的一种算法。下面我们给出这和算法的代码，希望读者们能够自己先写写代码再copy。下图是运行结果。
/* C++ implementation to convert infix expression to postfix*/
// Note that here we use std::stack for Stack operations
#include <iostream>
#include<stack>
using namespace std;
//Function to return precedence of operators
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s)
{
std::stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];
// If the scanned character is an ‘(‘, push it to the stack.
else if(s[i] == '(')
st.push('(');
// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}
//If an operator is scanned
else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}
}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}
cout << ns << endl;
}
//Driver program to test above functions
int main()
{
string exp = "a+b*c+(d*e+f)*g";
infixToPostfix(exp);
return 0;
}
