AOJ 1602 ICPC計算機
問題ページ
ICPC Calculator | Aizu Online Judge
解法
+か*が来たらその演算子で計算する範囲の数式を全部計算して返すような関数をつくってその関数を再帰的に呼び出していくことで計算する。ある演算子で計算する対象はその演算子より高さが1段高いものなのでそれより低いものが来たらその演算子の範囲は終了したと判定できる。n=1だと演算子が一つもないのに要注意。
再帰降下型の構文解析みたいな気持ちで考えたら実装どうやるかなんとなく決めれたけど細かい実装でindexバグらせたり<と<=間違えたりしていた。境界で混乱するときはちゃんと考えてから実装に移るべき。
#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back #ifdef int const ll INF = (1LL<<60); #else const int INF = (1LL<<30); #endif const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; string s[100]; pair<int, char> p[100]; int n; int add(int&, int); int mul(int&, int); int add(int& idx, int par) { int ret = 0; while(idx < n) { if(p[idx].first <= par) { break; } else if(p[idx].second == '+') { idx++; ret += add(idx, p[idx-1].first); } else if(p[idx].second == '*') { idx++; ret += mul(idx, p[idx-1].first); } else { ret += p[idx].second - '0'; idx++; } } return ret; } int mul(int &idx, int par) { int ret = 1; while(idx < n) { if(p[idx].first <= par) { break; } else if(p[idx].second == '+') { idx++; ret *= add(idx, p[idx-1].first); } else if(p[idx].second == '*') { idx++; ret *= mul(idx, p[idx-1].first); } else { ret *= p[idx].second - '0'; idx++; } } return ret; } signed main(void) { while(true) { cin >> n; if(!n) break; REP(i, n) cin >> s[i]; REP(i, n) p[i].first = 0; REP(i, n) { REP(j, s[i].size()) { if(s[i][j] == '.') p[i].first++; else p[i].second = s[i][j]; } } if(n == 1) { cout << p[0].second << endl; continue; } int ret; if(p[0].second == '+') { int st = 1; ret = add(st, 0); } else { int st = 1; ret = mul(st, 0); } cout << ret << endl; } return 0; }