ICPC Calculator

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1602&lang=ja

AC

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4007025#1

解法

• 入力をN行全部読み込んで後ろから処理
• サンプル

10
+
.+
..6
..2
.+
..1
..*
...7
...6
.3

• 文字列 ".3"はレベル1, 数字3なので(1, 3)としてスタックに積む
• 同様に、(3, 6), (3, 7)を積む
• 次に演算子, レベル2の＊が出てきたので、スタック上のレベル3のものを演算子で処理する。今回の場合、7＊6=42である
• 結果の42を、レベル2の42として積む (2, 42)
• 以下同様

Code

bool is_operator(string s){
  if(s.find('+')!=s.npos) return true;
  if(s.find('*')!=s.npos) return true;
  return false;
}

bool is_multiply(string s){
  if(s.find('*')!=s.npos) return true;
  return false;
}

// "...2" => 3
ll level(string s){
  ll L = s.size();
  ll cnt = 0;
  rep(i, L){
    if(s[i]=='.') cnt++;
  }
  return cnt;
}

// "...2" => 2
ll num(string s){
  ll i = 0;
  while(s[i]=='.'){
    i++;
  }
  string sub = s.substr(i);
  return stoll(sub);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    while(cin>>N){
      if(N==0) return 0;
      if(N==1){
        ll v; cin >> v;
        p(v);
        continue;
      }

      VS S(N);
      rep(i, N){
        cin >> S[i];
      }
      reverse(ALL(S));

      stack<pair<ll,ll>> st;
      rep(i, N){
        string s = S[i];
        if(is_operator(s)){
          ll lv = level(s);
          if(is_multiply(s)){
            ll mul = 1;
            while(st.size()>0 && st.top().first == lv+1){
              mul *= st.top().second;
              st.pop();
            }
            st.push(make_pair(lv, mul));
          }
          else{
            ll sum = 0;
            while(st.size()>0 && st.top().first == lv+1){
              sum += st.top().second;
              st.pop();
            }
            st.push(make_pair(lv, sum));
          }
        }
        else{
          // 数字
          ll lv = level(s);
          ll n = num(s);
          st.push(make_pair(lv, n));
        }
      }
      // 全部終えたら
      ll ans = st.top().second;
      p(ans);
    }
    return 0;
}

目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦