Algorithms/InfixToPostfix at master · LsDimple/Algorithms · 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
Q: Write a filter that converts an arithmetic expression from infix to postfix.

A: 使用一个队列和栈，普通数字直接入队列，操作符入栈；当待入栈的操作符比栈顶元素优先级高时，直接入栈；
当待入栈的操作符比栈顶元素优先级低时，依次出栈并入队列，直到栈顶元素的优先级低于当前待入栈操作符的优先级。
另外，操作符与'('之间忽略优先级比较，直接入栈；当待入栈字符为')'时，依次出栈并入队列，直到栈顶元素为'('为止。

string infixtopostfix(const string seq)
{
    stack<char> st;
    deque<char> qu;
    const map<char, int> op = { {'#', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };

    st.push('#');

    for (auto it : seq) {
        if (it >= 'a' && it < 'z') {
            qu.push_back(it);
        } else if (it == '(') {
            st.push(it);
        } else if (it == ')') {
            while (st.top() != '#' && st.top() != '(') {
                qu.push_back(st.top());
                st.pop();
            }
            st.pop(); // pop('(')
        } else {
            while (st.top() != '(' && st.top() != '#') {
                if (op.at(it).second == 0 && (op.at(it).first - op.at(st.top()).first <= 0)) { // left-associative
                    qu.push_back(st.top());
                    st.pop();
                    continue;
                }
                if (op.at(it).second == 1 && (op.at(it).first - op.at(st.top()).first < 0)) {
                    qu.push_back(st.top());
                    st.pop();
                    continue;
                }
                break;
            }
            st.push(it);
        }
    }

    while (st.top() != '#') {
        qu.push_back(st.top());
        st.pop();
    }
    return string(begin(qu), end(qu));
}

double evalutePostfix(const string s)
{
    stack<double> st;

    for (const auto &c : s) {
        if (c >= '0' && c <= '9') {
            st.push(c-'0');
            continue;
        }

        double op1, op2;
        op2 = st.top(); st.pop();
        op1 = st.top(); st.pop();
        switch (c) {
        case '+':
            st.push(op1+op2);
            break;
        case '-':
            st.push(op1-op2);
            break;
        case '*':
            st.push(op1*op2);
            break;
        case '/':
            st.push(op1/op2);
            break;
        case '^':
            st.push(pow(op1, op2));
            break;
        }
    }

    return st.top();
}