c++堆栈的应用：中缀表达式转化为后缀表达式

1、首先假设我们需要转化的中缀表达式为：a + b * c + ( d * e + f ) * g正确转化结果应为：a b c * + d e * f + g * +（字母代表一种操作数，+、*为操作符）下面介绍一下基于堆栈的算法。堆栈用于存储操作符。

3、如果扫描到的字符是一个操作符，分三种情况：（1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）（2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）（3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。

4、如果遇到的操作符是左括号"（”，就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。

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 operatorsint 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 expressionvoid 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 functionsint main(){ string exp = "a+b*c+(d*e+f)*g"; infixToPostfix(exp); return 0;}