AOJ 2570 Shipura
解法
> が >> なのか S < expr > の > なのかは,数字またはSの直前かどうかで判定ができる.
なので最初に式を後ろから見ていって,どれがシフト演算なのか確定させておく.
それができればあとは普通に左からパースするだけで十分.
シフト演算のときにシフトしすぎないように注意すること.
他の人は右から再帰的にやっていくという方法を取っていて,そっちのほうが良さそうだなーとは思った.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll M = 1e9+7; vector<bool> f; ll expr(string const& s, int& p); ll term(string const& s, int& p); void sp(string const& s, int& p); ll number(string const& s, int& p); ll expr(string const& s, int& p) { sp(s, p); ll v1 = term(s, p); sp(s, p); while(p+1 < s.size() && f[p]) { p += 2; sp(s, p); ll v2 = term(s, p); if(v2 > 63) { v1 = 0; } else { v1 >>= v2; } sp(s, p); } return v1; } ll term(string const& s, int& p) { sp(s, p); if(s[p] == 'S') { sp(s, ++p); p++; // < sp(s, p); ll v = expr(s, p); sp(s, p); p++; // > v = (v * v) % M; return v; } return number(s, p); } void sp(string const& s, int& p) { while(p < s.size() && s[p] == ' ') { p++; } } ll number(string const& s, int& p) { int res = 0; while(p < s.size() && isdigit(s[p])) { res *= 10; res += s[p++] - '0'; } return res; } int main() { while(true) { string s; getline(cin, s); if(s[0] == '#') { break; } int p = 0; f.assign(s.size(), false); for(int i=s.size()-1; i>=0; --i) { if(isdigit(s[i]) || s[i] == 'S') { if(isdigit(s[i])) { while(i > 0 && isdigit(s[i])) { --i; } } else if(s[i] == 'S') { i--; } while(i > 0 && s[i] == ' ') { i--; } if(s[i] == '>') { i--; f[i] = true; } } } cout << expr(s, p) << endl; } }