洛谷P1981《表达式求值》

十月 06, 2018 4666

新技能：手写计算器

题目描述

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

Input / Output 格式 & 样例

输入格式

一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“ + ”和乘法运算符“ \times ”，且没有括号，所有参与运算的数字均为 0 到 2^{31} 的整数。

输入数据保证这一行只有 0−9 、 + 、 \times 这 12 种字符。

输出格式

一个整数，表示这个表达式的值。

注意：当答案长度多于 4 位时，请只输出最后 4 位，前导 0 不输出。

输入样例

Case #1:

1
1+1*3+4

Case #2:

1
1+1234567890*1

Case #3:

1
1+1000000003*1

输出样例

Case #1:

1
8

Case #2:

1
7891

Case #3:

1
4

数据范围

对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；

对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；

对于100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。

解题思路

我们开两个单调栈，一个栈num来存储数字，一个栈operators来存储符号

其中operators的操作逻辑是这样的：

  • 首先把~push进去，作为一个占位符
  • 我们对运算符标一个优先级，规定~ < + < *且相同运算符优先级低（满足从左到右的运算顺序），写一个判断函数
  • 当push进去的运算符优先级比栈顶的低时，解决所有优先级低的运算符（维护单调性质）再push进去
  • 当push进去的运算符优先级比栈顶的高时，不用管，直接push进去（满足单调性质）

处理完输入之后，我们再对数字栈里剩下的数字进行处理

最后输出即可

代码实现

这里面所有的注释都是我在DEBUG的时候手推的样例

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
108
109
110
111
112
113
114
115
116
117
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    stack<int> num;
    stack<int> operators;
    // 1: + -
    // 2: * /
    
    const int MOD = 10000;
    long long int ans = 0;
    
    bool Priority(char op1, char op2) {
        // false -> op1 is lower
        // true -> op1 is higher
        if (op1 == op2) return false;
        if (op1 == '~') return false;
        if (op1 == '+' && op2 == '*') return false;
        if (op1 == '*' && op2 == '+') return true;
    }
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
    #endif
    using namespace Solution;
    using namespace FastIO;
    // 1+1*3+4
    int ans = 0, now = 0;
    char op = 0;
    cin >> ans; // 1
    num.push(ans % MOD); // < 1
    operators.push('~'); // < ~
    while (cin >> op >> now) { // +1 // *3 // +4
        char op1 = operators.top(); // ~ // + // *
        while (Priority(op1, op)) { // false // false // true // false
            int opNum = num.top(); // // // 3
            num.pop(); // // //  < 1 1
            int opNum2 = num.top(); // // // 1
            num.pop(); // // // < 1 
            if (op1 == '+') num.push((opNum + opNum2) % MOD); // // // false
            if (op1 == '*') num.push(opNum * opNum2 % MOD); // // // < 1 3
            operators.pop(); // < +
            op1 = operators.top(); // +
        }
        operators.push(op); // < + // < + * // < + +
        num.push(now); // < 1 1 // < 1 1 3 // < 1 3 4
    }
    while (num.size() > 1) { // true // true // false
    	int op = num.top(); // 4 // 7
    	num.pop(); // < 1 3 // < 1
    	int op2 = num.top(); // 3 // 1
    	num.pop(); // < 1 // <
    	char ope = operators.top();
    	operators.pop();
        if (ope == '+') num.push((op + op2) % MOD); // < 1 7 // < 8
        if (ope == '*') num.push(op * op2 % MOD);
    }
    FastIO::putint(num.top() % MOD, '\n'); // 8
    return 0;
}