Algoogle

Algorithm for Programming Contest

AOJ 2570 Shipura

Category: AOJ Tag: parsing

Shipura

問題概要


解法


数字か’S’の前の’>’は必ずシフト演算なので, それらをまず検出して別の記号に替えておく. 今回は$ 頭から構文解析していくのは演算の順番的にもなんかつらいので, 後ろから再帰的にやるのが楽でよい.
右から順に見ていくようにcurを定める.
exprは後ろから見たら必ずtermが最初に現れるのでそのままとりあえずtermを呼ぶ.
戻ってきたら, もし’<’だったらそのまま返す(termに呼ばれたexprなので). そうじゃなければ’$’のはずなのでcurを一個進めてさらにexprを呼んだ結果を前のtermの結果分シフトして返す.
termは後ろから見たら数字か’>’なので’>’だったらcurを1個進めてexprを呼ぶ. 戻ってきたら”S<”の文だけcurを進める. 数字だったらnumberを呼ぶ.
numberは数値を返すだけ.

シフトする時にいっぱいシフトしちゃうと変な数が出てきちゃうので, ある程度で0になることを利用して, 最大でも31ぐらいまでしかシフトしないようにする.

コード


(2570.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <iostream>
#include <string>

#define int long long
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) (u).begin(),(u).end()
#define pb push_back

using namespace std;

string str;
int cur;
const int mod = 1000000007;

bool input(){
    str.clear();
    cur = 0;
    string tmp;
    getline(cin, tmp);
    if(tmp == "#") return 0;
    for(auto &c : tmp)if(c != ' ') str.pb(c);
    return 1;
}

void convert(){
    repi(i,3,str.size())
        if(((str[i] >= '0' && str[i] <= '9') || str[i] == 'S') &&
           str[i-1] == '>' && str[i-2] == '>'){
            str[i-2] = '$';
            str.erase(str.begin() + i - 1, str.begin() + i);
            i++;
        }
}

int number(){
    string ret;
    while(cur < str.size() && str[cur] >= '0' && str[cur] <= '9')
        ret.pb(str[cur++]);
    reverse(all(ret));
    return atoi(ret.c_str());
}

int expr();

int term(){
    if(str[cur] == '>'){
        cur++;
        int t = expr();
        cur += 2;
        return t * t % mod;
    }
    else return number();
}

int expr(){
    int right = term();
    if(cur >= str.size()) return right;
    if(str[cur] == '<')  return right;
    else{
        cur++;
        return expr() >> min(right, 31LL);
    }
}

int solve(){
    convert();
    reverse(all(str));
    return expr();
}

signed main(){
    while(input()){ cout << solve() << endl;}
    return 0;
}

Comments