50242. Parse a boolean expression
難度：5/5
Used Time 31:341
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#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
enum exps{NOT, AND, OR, L_BR, R_BR, TRUE, FALSE};
typedef struct{
int val;
int is_valid;
int end_idx;
} info;
#define max(a,b) ((a)>(b)?(a):(b))
info solve(int arr[], int l, int n){
// for(int i = l; i < n; i++) printf("%d ", arr[i]); printf("\n");
if(l == n) return (info) {0, 0, 0};
if(arr[l] == AND || arr[l] == OR || arr[l] == R_BR) return (info) {0, 0, 0};
if(arr[l] == NOT){
info next = solve(arr, l + 1, n);
if(next.is_valid) return (info) {!next.val, 1, next.end_idx};
else return (info) {0, 0, 0};
}
else if(arr[l] == TRUE || arr[l] == FALSE){
return (info) {arr[l] == TRUE, 1, l + 1};
}
else if(arr[l] == L_BR){
info left = solve(arr, l + 1, n);
if(!left.is_valid) return (info) {0, 0, 0};
int op = arr[left.end_idx];
info right = solve(arr, left.end_idx + 1, n);
if(!right.is_valid) return (info) {0, 0, 0};
if(right.end_idx == n || arr[right.end_idx] != R_BR) return (info) {0, 0, 0};
if(op == AND) return (info) {left.val && right.val, 1, right.end_idx + 1};
else if(op == OR) return (info) {left.val || right.val, 1, right.end_idx + 1};
else return (info) {0, 0, 0};
}
else return (info) {0, 0, 0};
}
int main(){
char s[2005]; int arr[512];
while(fgets(s, 2005, stdin) != NULL){
char* token = strtok(s, " \n");
int n = 0;
int is_valid = 1;
while(token != NULL){
if(strcmp(token, "!") == 0) arr[n++] = NOT;
else if(strcmp(token, "&&") == 0) arr[n++] = AND;
else if(strcmp(token, "||") == 0) arr[n++] = OR;
else if(strcmp(token, "(") == 0) arr[n++] = L_BR;
else if(strcmp(token, ")") == 0) arr[n++] = R_BR;
else if(strcmp(token, "true") == 0) arr[n++] = TRUE;
else if(strcmp(token, "false") == 0) arr[n++] = FALSE;
else{
is_valid = 0;
break;
}
token = strtok(NULL, " \n");
}
if(is_valid){
info ans = solve(arr, 0, n);
if(ans.is_valid && ans.end_idx == n){
if(ans.val) printf("true\n");
else printf("false\n");
}
else{
printf("invalid\n");
}
}
else{
printf("invalid\n");
}
}
}