栈的应用——后缀表达式

1.思想

目标：将中缀表达式转换为后缀表达式

思想：

• 读到一个操作数时，放到输出中
• 读到一个操作符时（包括左括号），从占中弹出元素并加入到输出中，直到发现更低的优先级的元素，再将操作符入栈。有一个例外，在未出现右括号时，绝不弹出左括号
• 读到右括号时，弹出栈元素，直至遇到左括号，弹出的元素中，除左括号都加入输出中
• 读到序列末尾，将栈中所有元素弹出，加入到输出中

2.实现

string convertPostFix(const string &expr)
{//优先级map<char, int> ops;ops['('] = 3;ops['*'] = 2;ops['+'] = 1;ops[')'] = 3;string res = "";stack<char> stk;for (char item : expr){//操作数if (isalpha(item))res.push_back(item);//操作符if (item == '*' || item == '+'||item=='('){char temp;while (!stk.empty()){temp = stk.top();if (temp == '(')break;if (ops[temp] >= ops[item]){res.push_back(temp);stk.pop();}elsebreak;	}stk.push(item);}//括号if (item == ')'){char temp;while (!stk.empty()){temp = stk.top();if (temp == '(') {stk.pop(); break;}else{res.push_back(temp);stk.pop();}}}}while (!stk.empty()){res.push_back(stk.top());stk.pop();}return res;
}

3.实例

输入：a+b*c+(d*e+f)*g
输出：abc*+de*f+g*+