土下座しながら探索中

主に競技プログラミング

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;
}