VIRTUALS

the virtual labs for the virtuals

0%

【AcWing算法基础】第二讲-数据结构-栈 AcWing 3302. 表达式求值

Posted on Edited on In , , , ,

摘要：
一道表达式求值问题，可以使用非递归的栈解法。

题目

定一个表达式，其中运算符仅包含 $+,-, \times,/$（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，$-1+2$, $(2+2) \times (-(1+1)+2)$ 之类表达式均不会出现。
  • 题目保证表达式中所有数字均为正整数。
  • 题目保证表达式在中间计算过程以及结果中，均不超过 $231−1$。
  • 题目中的整除是指向 $0$ 取整，也就是说对于大于 $0$ 的结果向下取整，例如 $5/3=1$，对于小于 $0$ 的结果向上取整，例如 $5/(1−4)=−1$。
  • C++和Java中的整除默认是向零取整；Python中的整除 // 默认向下取整，因此Python的 eval() 函数中的整除也是向下取整，在本题中不能直接使用。

输入格式
共一行，为给定表达式。

输出格式
共一行，为表达式的结果。

数据范围
表达式的长度不超过 105。

输入样例：

$(2+2) \times (1+1)$

输出样例：

8

栈

我们维护两个栈，一个放操作符号，另一个放数字。
原则是这样：

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
#include <bits/stdc++.h>

using namespace std;

stack<int> nums;
stack<char> ops;

unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

inline void eval()
{
    int b = nums.top(); nums.pop(); // the top of stk should be the secondary number
    int a = nums.top(); nums.pop();
    char op = ops.top(); ops.pop();
    int res;
    if (op == '+') res = a + b;
    else if (op == '-') res = a - b;
    else if (op == '*') res = a * b;
    else res = a / b;
    nums.push(res);
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (isdigit(c)) {
            int j = i;
            int x = 0;
            for (; j < n && isdigit(s[j]); j++) {
                x = x * 10 + (s[j] - '0');
            }
            i = j - 1;  // because i++ later
            nums.push(x);
        }
        else if (c == '(') {
            ops.push(c);
        }
        else if (c == ')') {
            for (; ops.top() != '('; eval());
            ops.pop();
        }
        else {
            // determine the priority
            // compare the operator between the last operator on the stk and current operator
            for (; ops.size() && ops.top() != '(' && pr[ops.top()] >= pr[c]; eval());
            ops.push(c);
        }
    }
    // the last entity could be a digital, since needs to do eval process once again
    // if the operation stack contains several operations and the previous ops has a lower priority than the later's, we have to loop eval that
    for (; ops.size(); eval());
    //for (; nums.size(); nums.pop()) cout << nums.top() << endl;
    cout << nums.top() << endl;
    return 0;
}
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;

public class Main {

    private static LinkedList<Character> ops = new LinkedList<>();
    private static LinkedList<Integer> nums = new LinkedList<>();
        
    private static void eval() {
        int b = nums.removeLast();
        int a = nums.removeLast();
        char op = ops.removeLast();
        int res;
        if (op == '+') res = a + b;
        else if (op == '-') res = a - b;
        else if (op == '*') res = a * b;
        else res = a / b;
        nums.addLast(res);
    }
    
    public static void solve(char[] chs) {
        Map<Character, Integer> pr = new HashMap<>();
        pr.put('+', 1);
        pr.put('-', 1);
        pr.put('*', 2);
        pr.put('/', 2);
        int n = chs.length;
        for (int i = 0; i < n; i++) {
            Character c = chs[i];
            if (Character.isDigit(c)) {
                int j = i;
                int x = 0;
                for (; j < n && Character.isDigit(chs[j]); x = x * 10 + chs[j++] - '0');
                i = j - 1;
                nums.addLast(x);
                //System.out.println(x);
            } else if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                for (; !ops.isEmpty() && ops.peekLast() != '('; eval());
                ops.removeLast();
            } else {
                for (; !ops.isEmpty() && ops.peekLast() != '(' && pr.get(ops.peekLast()) >= pr.get(c); eval());
                ops.addLast(c);
            }
        }
        for (; !ops.isEmpty(); eval());
        System.out.println(nums.peekLast());
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        char[] chs = s.toCharArray();
        solve(chs);
    }
}

原题链接： AcWing 3302. 表达式求值