第三题

题目描述

输入一个字符串计算表达式，用递归计算其正确输出结果，结果只截取整数部分。要求：字符串中每个数字只能在0-9之间，其余只能包含英文‘+’、‘-’、‘*’、‘/’四个运算符和小括号()，如有其它字符输入，统一输出“ERROR”提示。注意输入不包括空格，以Enter键作为输入结束符。

输入描述

每次输入为一个表达式：如1+2*3-(5-4)+6/3。

输出描述

输出该表达式的值：如8

分析

  • 用逆波兰法可解决。参考：波兰式、逆波兰式与表达式求值

  • 逆波兰法：先将中缀表达式转换成后缀表达式，然后再利用后缀表达式求解。

  • 中缀表达式转换成后缀表达式步骤：

    • 从左至右依次遍历表达式中元素；
    • 如果当前元素是数字，直接输出；
    • 如果当前元素是左括号，压入栈中；
    • 如果当前元素是操作符，执行while循环：
      • 如果满足栈为空或栈顶元素为左括号或当前操作符优先级高于栈顶操作符优先级，将当前元素压入栈中，并退出while循环；
      • 否则，栈顶元素出栈并输出，并继续while循环。
    • 如果当前元素是右括号，则栈顶元素出栈并输出，直至遇到左括号，将左括号丢弃；
    • 遍历结束后，输出栈中所有元素。

  • 后缀表达式求解步骤：

    • 从左至右遍历后缀表达式中元素；
    • 如果是数字，压入栈内；
    • 如果是操作符，从栈中取出两个数进行操作，并将结果压入栈中（出二进一）
    • 遍历结束年，栈顶元素即为结果。
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
// 判断是否是表达式
bool isExpr(string s) {
    bool ret = true;
    for (int i = 0; i < s.size(); ++i) {
        if (!((s[i] >= '0' && s[i] <= '9') || s[i] == '+' || s[i] == '-' || 
            s[i] == '*' || s[i] == '/' || s[i] == '(' || s[i] == ')')) {
            ret = false;
            break;
        }
    }
    return ret;
}

// 判断是否是操作符
bool isOperator(const char& op) {
    return (op == '+' || op == '-' || op == '*' || op == '/');
}

// 返回运行符的优先级
int priority(const char& op) {
    if (op == '*' || op == '/')
        return 2;
    else if (op == '+' || op == '-')
        return 1;
    else
        return 0;
}

// 中缀表达式转换成后缀表达式
void infix2Suffix(const string& src, string& dst) {
    stack<char> s;
    for (int i = 0; i < src.size(); ++i) {
        // 如果是数字，直接输出
        if (src[i] <= '9' && src[i] >= '0')
            dst += src[i];
        // 如果是左括号，压入栈中
        if (src[i] == '(')
            s.push(src[i]);
        // 如果是操作符
        while (isOperator(src[i])) {
            // 当栈为空或栈顶为左括号或当前操作符优先级高于栈顶操作符优先级时，压入栈中，并退出while循环
            if (s.empty() || s.top() == '(' || priority(src[i]) > priority(s.top())) {
                s.push(src[i]);
                break;
            }
            // 否则，将栈顶元素出栈，并继续while循环
            else {
                dst += s.top();
                s.pop();
            }
        }
        // 如果是右括号，则不停地执行出栈操作直至栈顶元素为左括号，最后丢弃掉左括号
        if (src[i] == ')') {
            while (src[i] != '(') {
                dst += s.top();
                s.pop();
            }
            s.pop();
        }
    }
    
    // 遍历结束后将栈中剩下元素输出
    while (!s.empty()) {
        dst += s.top();
        s.pop();
    }
}

// 求解
int getResult(const string& src) {
    string dst;
    stack<int> s;
    infix2Suffix(src, dst);
    
    for (int i = 0; i < dst.size(); ++i) {
        if (dst[i] <= '9' && dst[i] >= '0')
            s.push(dst[i] - '0');
        else {
            int a = s.top();
            s.pop();
            int b = s.top();
            s.pop();
            int c = 0;
            if (dst[i] == '+')
                c = b + a;
            else if (dst[i] == '-')
                c = b - a;
            else if (dst[i] == '*')
                c = b * a;
            else if (dst[i] == '/')
                c = b / a;
            s.push(c);
        }
    }
    return s.top();
}

int main() {
    string expr;
    while(cin >> expr) {
        if (!isExpr(expr))
            cout << "ERROR" << endl;
        else
            cout << getResult(expr) << endl;
    }
    return 0;
}