Algoogle

Algorithm for Programming Contest

AOJ 2401 Equation

Category: AOJ Tag: parsing

Equation

問題概要


解法


まずequationを読んで, formulaで再帰的に分析して後置式に直していく.
後置式の計算は楽.
実装が面倒で細かい所に注意しないとバグ祭りになる.

コード


(2401.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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define mp make_pair

map<char,int> id;
int cnt;

char rogic(char a, char b, char op){
    bool x = (a=='T')? true: false;
    bool y = (b =='T')? true: false;
    if(op == '-') return (!x? 'T': 'F');
    if(op == '*') return (x&y? 'T': 'F');
    if(op == '+') return (x|y? 'T': 'F');
    if(op == '>') return (x<=y? 'T': 'F');
}

bool calc(pair<string,string> eq){
    rep(i,1<<cnt){
        string left = eq.first;
        string right = eq.second;
        char l, r;
        rep(cur,left.size()){
            if(left[cur]>='a' && left[cur]<='k')
                left[cur] = (i&(1<<id[left[cur]]))? 'T': 'F';
            else if(left[cur]=='-'){
                char res = rogic(left[cur-1],'T','-');
                left.replace(cur-1,2,1,res);
                cur--;
            }else if(left[cur]=='+' || left[cur]=='*' || left[cur]=='>'){
                char res = rogic(left[cur-2],left[cur-1],left[cur]);
                left.replace(cur-2,3,1,res);
                cur-=2;
            }
        }
        rep(cur,right.size()){
            if(right[cur]>='a' && right[cur]<='k')
                right[cur] = (i&(1<<id[right[cur]]))? 'T': 'F';
            else if(right[cur]=='-'){
                char res = rogic(right[cur-1],'T','-');
                right.replace(cur-1,2,1,res);
                cur--;
            }else if(right[cur]=='+' || right[cur]=='*' || right[cur]=='>'){
                char res = rogic(right[cur-2],right[cur-1],right[cur]);
                right.replace(cur-2,3,1,res);
                cur-=2;
            }
        }
        if(left!=right) return false;
    }
    return true;
}

string formula(string str){
    string ret = "";
    int cur = 0;
    char op;

    while(cur < str.size()){
        if((str[cur]>='a' && str[cur]<='k') || str[cur]=='T' || str[cur]=='F') ret += str[cur++];
        else if(str[cur]=='-' && str[cur+1]!='>'){
            int mcnt = 0;
            while(str[cur]=='-'){
                mcnt++;
                cur++;
            }
            if(str[cur]=='('){
                string form = "(";
                int kakko = 1;
                cur++;
                while(kakko){
                    if(str[cur]=='(') kakko++;
                    else if(str[cur]==')') kakko--;
                    form += str[cur];
                    cur++;
                }
                ret += formula(form);
            }else ret += str[cur++];
            if(mcnt%2) ret += '-';
        }else if(str[cur]=='('){
            int mcnt = 0;
            string form = "";
            cur++;
            while(str[cur]=='-'){
                mcnt++;
                cur++;
            }
            if(mcnt%2) form += '-';
            if(str[cur]=='('){
                form += '(';
                int kakko = 1;
                cur++;
                while(kakko){
                    if(str[cur]=='(') kakko++;
                    else if(str[cur]==')') kakko--;
                    form += str[cur];
                    cur++;
                }
                ret += formula(form);
            }else{
                form += str[cur++];
                ret += formula(form);
            }

            op = str[cur++];
            if(op == '-') op = str[cur++];

            mcnt = 0;
            form = "";
            while(str[cur]=='-'){
                mcnt++;
                cur++;
            }
            if(mcnt%2) form += '-';
            if(str[cur]=='('){
                form += '(';
                int kakko = 1;
                cur++;
                while(kakko){
                    if(str[cur]=='(') kakko++;
                    else if(str[cur]==')') kakko--;
                    form += str[cur];
                    cur++;
                }
                ret += formula(form);
            }else{
                form += str[cur++];
                ret += formula(form);
            }
            ret += op;
            cur++;
        }
    }
    return ret;
}

pair<string,string> equation(string str){
    string retl = "", retr = "";
    int cur = 0;
    while(str[cur] != '='){
        retl += str[cur];
        if(str[cur]>='a' && str[cur]<='k' && id.find(str[cur])==id.end()){
            id[str[cur]] = cnt++;
        }
        cur++;
    }
    cur++;
    while(cur<str.size()){
        retr += str[cur];
        if(str[cur]>='a' && str[cur]<='k' && id.find(str[cur])==id.end()){
            id[str[cur]] = cnt++;
        }
        cur++;
    }
    retl = formula(retl);
    retr = formula(retr);

    return mp(retl,retr);
}

int main(){
    string str;
    while(cin>>str,str!="#"){
        id.clear(); cnt = 0;
        pair<string,string> eq = equation(str);
        cout << (calc(eq)? "YES\n": "NO\n");
    }
    return 0;
}

Comments