50211. Expression

難度：5/5

Second Try: 4/5 Used Time: 16:27

version 1

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>

#define is_opr(c) (((c) == '+') || ((c) == '-') || ((c) == '*') || ((c) == '/'))
#define max(a,b) ((a)>(b)?(a):(b))

typedef struct{
    int val;
    char is_valid;
    int end_idx;
} info;

int n;
char s[1000005];
info not_valid;

info eval_base(int l)
{
    int ans = 0;
    int i;
    for(i = l; i < n && isdigit(s[i]); i++){
        ans = ans * 10 + (s[i] - '0');
    }
    if(i == l || i == n) return not_valid;

    info rtv;
    rtv.val = ans;
    rtv.is_valid = 1;
    rtv.end_idx = i;
    return rtv;
}

info solve(int l)
{
    if(s[l] != '('){
        return not_valid;
    }
    if(s[l + 1] == '(')
    {
        info left = solve(l + 1);
        if(!left.is_valid) return not_valid;
        if(left.end_idx == n || !is_opr(s[left.end_idx])) return not_valid;

        info right = solve(left.end_idx + 1);
        if(!right.is_valid) return not_valid;
        if(right.end_idx == n || s[right.end_idx] != ')') return not_valid;

        info ans;
        if(s[left.end_idx] == '+') ans.val = left.val + right.val;
        else if(s[left.end_idx] == '-') ans.val = left.val - right.val;
        else if(s[left.end_idx] == '*') ans.val = left.val * right.val;
        else if(s[left.end_idx] == '/') ans.val = left.val / right.val;
        ans.is_valid = 1;
        ans.end_idx = right.end_idx + 1;
        return ans;
    }
    else if(isdigit(s[l + 1]))
    {
        info left = eval_base(l + 1);
        if(!left.is_valid) return not_valid;
        if(left.end_idx == n || !is_opr(s[left.end_idx])) return not_valid;

        info right = eval_base(left.end_idx + 1);
        if(!right.is_valid) return not_valid;
        if(right.end_idx == n || s[right.end_idx] != ')') return not_valid;

        info ans;
        if(s[left.end_idx] == '+') ans.val = left.val + right.val;
        else if(s[left.end_idx] == '-') ans.val = left.val - right.val;
        else if(s[left.end_idx] == '*') ans.val = left.val * right.val;
        else if(s[left.end_idx] == '/') ans.val = left.val / right.val;
        ans.is_valid = 1;
        ans.end_idx = right.end_idx + 1;
        return ans;
    }
    else{
        return not_valid;
    }
}


int main()
{
    not_valid.is_valid = 0;
    while(scanf("%s", s) != EOF)
    {
        n = strlen(s);
        info rtv = solve(0);
        if(rtv.is_valid == 1 && rtv.end_idx == n) printf("%d\n", rtv.val);
        else printf("invalid\n");
    }
}

version 2 (by B06902061)

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>

#define is_op(c) (((c) == '+') || ((c) == '-') || ((c) == '*') || ((c) == '/'))
#define is_dig(c) (((c) >= '0') && ((c) <= '9'))
#define max(a,b) ((a)>(b)?(a):(b))

typedef struct{
    int is_valid;
    int val;
    int next_idx;
} info;

int n;
char s[1000005];

info eval_num(int start){
    int ans = 0;
    while(is_dig(s[start]) && start < n){
        ans = ans * 10 + (s[start] - '0');
        start++;
    }
    return (info) {1, ans, start};
}

info solve(int start){
    info l, r; char op;
    if(s[start] == '('){
        start++;
        if(is_dig(s[start])){
            l = eval_num(start);
            op = s[l.next_idx];
            if(!is_dig(s[l.next_idx + 1])) return (info) {0, 0, 0};
            r = eval_num(l.next_idx + 1);
        }
        else if(s[start] == '('){
            l = solve(start);
            op = s[l.next_idx];
            if(s[l.next_idx + 1] != '(') return (info) {0, 0, 0};
            r = solve(l.next_idx + 1);
        }
    }
    else{
        return (info) {0, 0, 0};
    }

    if((!l.is_valid) || (!r.is_valid) || (!is_op(op)) || (s[r.next_idx]) != ')'){
        return (info) {0, 0, 0};
    }

    if(op == '+') return (info) {1, l.val + r.val, r.next_idx + 1};
    if(op == '-') return (info) {1, l.val - r.val, r.next_idx + 1};
    if(op == '*') return (info) {1, l.val * r.val, r.next_idx + 1};
    if(op == '/') return (info) {1, l.val / r.val, r.next_idx + 1};
}

int main(){
    while(scanf("%s", s) != EOF){
        n = strlen(s);
        info rtv = solve(0);
        if(rtv.is_valid == 1 && rtv.next_idx == n) printf("%d\n", rtv.val);
        else printf("invalid\n");
    }
}

Coding > Solutions > Judge Girl > 2021
#implementation#string#recursion#parsing#IMPORTANT
50211. Expression
https://aaronlin1229.github.io/judgegirl_50211/
Author
Akizumi
Posted on
July 17, 2023
Licensed under