algorithm_study/calc_expression.cc at master · zhoubaozhou/algorithm_study · GitHub

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
#include <cassert>
#include <string>
#include <stack>
#include <iostream>

template<typename T>
typename T::value_type pop(T& stack) {
    typename T::value_type val = stack.top();
    stack.pop();
    return val;
}

int priority(int op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '(') return 0;
    assert(0);
}

int calc(char op, int x, int y) {
    switch(op) {
    case '+':
        return x + y;
    case '-':
        return x - y;
    case '*':
        return x * y;
    case '/':
        return x / y;
    default:
        assert(0);
    }
}

void calc_expression_in_bracket(std::stack<int>& num_stack, std::stack<char>& op_stack) {
    while (op_stack.top() != '(') {
        int y = pop(num_stack);
        int x = pop(num_stack);
        char op = pop(op_stack);
        num_stack.push(calc(op, x, y));
    }
    assert(op_stack.top() == '(');
    pop(op_stack);
}

int calc_expression(const std::string& expression) {
    std::stack<int> num_stack;
    std::stack<char> op_stack;

    std::string num_str;
    for (std::size_t i=0; i<expression.length(); ++i) {
        char c = expression[i];
        if (c >= '0' && c <= '9') {
            num_str.append(1, c);
            continue;
        }
        if (num_str.length() > 0) {
            num_stack.push(atoi(num_str.c_str()));
            num_str.clear();
        }
        if (c == ')') {
            calc_expression_in_bracket(num_stack, op_stack);
            continue;
        }
        if (c == '(' || op_stack.size() == 0 || priority(c) >= priority(op_stack.top())) {
            op_stack.push(c);
            continue;
        }
        while (op_stack.size() > 0 && priority(c) < priority(op_stack.top())) {
            int op = pop(op_stack);
            int y = pop(num_stack);
            int x = pop(num_stack);
            num_stack.push(calc(op, x, y));
        }
        op_stack.push(c);
    }
    if (num_str.length()) {
        num_stack.push(atoi(num_str.c_str()));
    }
    while (op_stack.size() > 0) {
        int op = pop(op_stack);
        int y = pop(num_stack);
        int x = pop(num_stack);
        num_stack.push(calc(op, x, y));
    }
    assert(num_stack.size() == 1);
    assert(op_stack.size() == 0);
    return num_stack.top();
}

int main() {
    std::cout << calc_expression("(5*1)+(2+3)*(4+5-2/1)") << std::endl;
    return 0;
}