ZeroJudge f377. 運算式轉換

題目連結

題意

把中序運算式轉換成後序運算式。

所謂中序跟後序運算式指的是運算元 （那些數字）跟運算子（+-/*）順序的不同排法
前序：運算子 運算元 運算元
中序：運算元 運算子 運算元
後序：運算元 運算元 運算子
也就是運算子出現的位置不同，所以中序的 3 + 2 就會變成後序的 3 2 +

解題方法

觀察題目給的範例可以發現，越左邊的運算子會越早被處理，因此
我們用一個 stack 來把所有的運算子儲存下來做處理：

• 遇到運算元的話就直接輸出
• 遇到優先級最高的刮號
  • 左刮號直接放進 stack 裡
  • 右刮號的話把 stack 直到上一個左刮號的運算子一一輸出
• 遇到優先及第二高的乘除
  • 如果現在 stack 最上面的運算子優先級 >= 乘除 ：把 stack 最上面的輸出，因為他們應該要在現在處理的運算子前先被處理，再把現在的運算子放入 stack
  • 反之，直接把現在的運算子放入 stack
• 遇到優先度最低的加減
  • 與乘除一樣，如果現在 stack 最上面的運算子優先級 >= 加減：把 stack 最上面的輸出，因為他們應該要在現在處理的運算子前先被處理，再把現在的運算子放入 stack .
  • 反之，直接把現在的運算子放入 stack

#include <bits/stdc++.h>
using namespace std;
int main() {
	string s, c;
	while(getline(cin, s)) {
		stack <string> st;
		vector <string> ans;
		stringstream ss; ss << s; 
		while(ss >> c) {
			if(c == ")") {
				while(st.top() != "(") {
					ans.push_back(st.top());
					st.pop();
				}
				st.pop();
			} else if(c == "(") {
				st.push("(");
			} else if(c == "*" || c == "/") {
				while(!st.empty() && (st.top() == "*" || st.top() == "/")) {
					ans.push_back(st.top());
					st.pop();
				} 
				st.push(c);
			} else if(c == "+" || c == "-") {
				while(!st.empty() && (st.top() == "*" || st.top() == "/" || st.top() == "+" || st.top() == "-")) {
					ans.push_back(st.top());
					st.pop();
				} 
				st.push(c);
			} else {
				ans.push_back(c);
			}
		}
		
		while(!st.empty()) {
			ans.push_back(st.top());
			st.pop();
		}
		for(int i = 0;i < ans.size();i++) {
			cout << ans[i] << " \n"[i == ans.size()-1];
		}
	}
}