UVa 727 : Equation
問題リンク:Equation
問題概要:
Infixで式が与えられる
Postfixに変換せよ
制約:
数字は1文字
解法:
スタックを用意する
式を左から右に向かって見ていく
以下の方法にしたがって変換する
・アルファベットが'('の場合、スタックにプッシュ
・アルファベットが数字の場合、出力する
・アルファベットが')'の場合、'('がくるまでスタックの頂点を出力した後にポップする
'('は出力せずにポップする
・アルファベットが演算子の場合、優先順位が自分と同等かそれ以上であるかぎり出力、ポップを繰り返す
式を見終わったら、スタックが空になるまで出力、ポップを繰り返す
pdfとhtmlで入力のしかたが違うのでhtmlの方に従う亊
outputとoutputの間には空行を1ついれること
コード:
#define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; void compute(vector<char> &vec) { stack<char> stk; rep(i,vec.size()) { if(vec[i] == '(') { stk.push(vec[i]); } else if('0' <= vec[i] && vec[i] <= '9') { cout << vec[i]; } else if(vec[i] == ')') { while(stk.top() != '(') { cout << stk.top(); stk.pop(); } stk.pop(); } else if(vec[i] == '*' || vec[i] == '/') { while(!stk.empty() && (stk.top() == '*' || stk.top() == '/')) { cout << stk.top(); stk.pop(); } stk.push(vec[i]); } else if(vec[i] == '+' || vec[i] == '-') { while(!stk.empty() && (stk.top() == '*' || stk.top() == '/' || stk.top() == '+' || stk.top() == '-')) { cout << stk.top(); stk.pop(); } stk.push(vec[i]); } } while(!stk.empty()) { cout << stk.top(); stk.pop(); } puts(""); } int main() { string line; int T; bool first = true; getline(cin,line); T = (atoi)(line.c_str()); getline(cin,line); assert(line.empty()); while(T) { vector<char> vec; while(getline(cin,line)) { if(line.empty()) { break; } vec.push_back(line[0]); } T--; if(!first)puts(""); first = false; compute(vec); } return 0; }