AOJ 1602: ICPC Calculator

問題

ICPC Calculator | Aizu Online Judge

国際反括弧会議が考えた変な記法に従って計算するプログラムを作れ

  • 各行は入れ子レベルを表す'.'・加算を表す'+'・乗算を表す'*'・整数からなる
  • 式の最初の行は入れ子レベルの数だけの'.'からなる
  • レベルnの演算子はそれ以降の行にあるレベルn+1の式に対して適用される

Lispの記法をイメージすると多分分かりやすくて

+
.2
.3

は

(+ 2 3)
*
.+
..2
..3
..4
.5

は

(* (+ 2 3 4) 5)

に対応する

方針

  • 整数のみの式ならその整数を返す
  • レベルnで演算子が来たら、レベルn+1の式全部に対して演算子を適用する
  • 再帰実行すれば何段でも対応できる

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

typedef pair<int, char> P;

int getLevel(string &expr) {
    int ret = 0;
    while(expr[ret] == '.') ret++;
    return ret;
}

bool isdigit(char c) {
    return c >= '0' && c <= '9';
}

int process(vector<string> &expr, int* line) {
    int ret;
    int level = getLevel(expr[*line]);
    if(level == 0 && isdigit(expr[*line][level])) 
        return expr[*line][level]-'0';
    else if(expr[*line][level] == '+') {
        (*line)++;
        ret = 0;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret += expr[*line][new_level]-'0';
                else 
                    ret += process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    } else if(expr[*line][level] == '*') {
        (*line)++;
        ret = 1;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret *= expr[*line][new_level]-'0';
                else 
                    ret *= process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    }
}

int main(void){
    int n;
    string s;
    vector<string> expr;
    while(cin >> n && n) {
        cin.ignore();
        expr.clear();
        rep(i, n) {
            getline(cin, s);
            expr.push_back(s);
        }
        int line = 0;
        cout << process(expr, &line) << endl;
    }
}

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

反省