[expression calculation] double stack: general solution of expression calculation problem

Title Description

This is a LeetCode Upper 224. Basic calculator , The difficulty is difficult .

Tag : 「 Expression evaluation 」

Here's a string expression for you s , Please implement a basic calculator to calculate and return its value .

Example 1：

 Input ：s = "1 + 1"

 Output ：2

Example 2：

 Input ：s = " 2-1 + 2 "

 Output ：3

Example 3：

 Input ：s = "(1+(4+5+2)-3)+(6+8)"

 Output ：23

Tips ：

• s from Numbers 、 '+'、 '-'、 '('、 ')'、 and ' ' form
• s Represents a valid expression

Double stack

We can use two stacks nums and ops .

• nums ： Store all the numbers
• ops ： Save all the numbers except for the operation , +/- It is also regarded as an operation

Then do it from front to back , The characters traversed are discussed in different cases ：

• Space : skip
• ( : Directly to join ops in , Waiting for a match )
• ) : Use the existing nums and ops Calculate , Until you encounter the nearest left parenthesis , The calculation results are put in nums
• Numbers : Continue to move back from the current position , Take out the whole continuous number as a whole , Join in nums
• +/- : The operation needs to be put into ops in . Before putting it into the stack, count out everything that can be counted , Use the existing nums and ops Calculate , Until there is no operation or left parenthesis , The calculation results are put in nums

Some details ：

• Since the first number may be negative , In order to reduce boundary judgment . One trick is to go first nums Add one 0
• To prevent () The first character that appears in the is the operator , Remove all spaces , And will (- Replace with (0-, (+ Replace with (0+（ Of course, such pretreatment can also be omitted , Put this processing logic into the loop to do ）

Java Code ：

class Solution {
    public int calculate(String s) {
        //  Store all the numbers 
        Deque<Integer> nums = new ArrayDeque<>();
        //  To prevent the first number from being negative , The first  nums  Add one  0
        nums.addLast(0);
        //  Remove all spaces 
        s = s.replaceAll(" ", "");
        //  Store all operations , Include  +/-
        Deque<Character> ops = new ArrayDeque<>();
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                //  Calculate to the nearest left parenthesis 
                while (!ops.isEmpty()) {
                    char op = ops.peekLast();
                    if (op != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNum(c)) {
                    int u = 0, j = i;
                    //  Will be taken from  i  The continuous numbers after the position start are taken out as a whole , Join in  nums
                    while (j < n && isNum(cs[j])) u = u * 10 + (int)(cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    //  When there is a new operation to be put on the stack , First of all, let's count everything that can be counted in the stack 
                    while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
                    ops.addLast(c);
                }
            }
        }
        while (!ops.isEmpty()) calc(nums, ops);
        return nums.peekLast();
    }
    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        nums.addLast(op == '+' ? a + b : a - b);
    }
    boolean isNum(char c) {
        return Character.isDigit(c);
    }
}

C++ Code ：

class Solution {
public:
    void replace(string& s){
        int pos = s.find(" ");
        while (pos != -1) {
            s.replace(pos, 1, "");
            pos = s.find(" ");
        }
    }
    int calculate(string s) {
        //  Store all the numbers 
        stack<int> nums;
        //  To prevent the first number from being negative , The first  nums  Add one  0
        nums.push(0);
        //  Remove all spaces 
        replace(s);
        //  Store all operations , Include  +/-
        stack<char> ops;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if(c == '(')
                ops.push(c);
            else if(c == ')') {
                //  Calculate to the nearest left parenthesis 
                while(!ops.empty()) {
                    char op = ops.top();
                    if(op != '(')
                        calc(nums, ops);
                    else {
                        ops.pop();
                        break;
                    }
                }
            }
            else {
                if(isdigit(c)) {
                    int cur_num = 0, j = i;
                    //  Will be taken from  i  The continuous numbers after the position start are taken out as a whole , Join in  nums
                    while(j <n && isdigit(s[j]))
                        cur_num = cur_num*10 + (s[j++] - '0');
                    //  Note that the above calculation must have brackets , Otherwise, it may overflow 
                    nums.push(cur_num);
                    i = j - 1;
                }
                else {
                    if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
                        nums.push(0);
                    }
                    //  When there is a new operation to be put on the stack , First of all, let's count everything that can be counted in the stack 
                    while(!ops.empty() && ops.top() != '(')
                        calc(nums, ops);
                    ops.push(c);
                }
            }
        }
        while(!ops.empty())
            calc(nums, ops);
        return nums.top();
    }
    void calc(stack<int> &nums, stack<char> &ops) {
        if(nums.size() < 2 || ops.empty())
            return;
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        nums.push(op == '+' ? a+b : a-b);
    }
};

• Time complexity ：
• Spatial complexity ：

Advanced

1. If on this basis , Think again * and /, What considerations need to be added ？ How to maintain the priority of operators ？
2. stay On the basis of , If you consider supporting custom symbols , for example a / func(a, b) * (c + d), What adjustments need to be made ？

Add

1. Corresponding advanced level 1 A supplement to .

One support + - * / ^ % Of 「 Calculator 」, The basic logic is the same , Maintain a symbol priority using a dictionary ：

class Solution {
    Map<Character, Integer> map = new HashMap<>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};
    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        char[] cs = s.toCharArray();
        int n = s.length();
        Deque<Integer> nums = new ArrayDeque<>();
        nums.addLast(0);
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNumber(c)) {
                    int u = 0;
                    int j = i;
                    while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (map.get(prev) >= map.get(c)) {
                            calc(nums, ops);
                        } else {
                            break;
                        }
                    }
                    ops.addLast(c);
                }
            }
        }
        while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
        return nums.peekLast();
    }
    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') {
            ans = a + b;
        } else if (op == '-') {
            ans = a - b;
        } else if (op == '*') {
            ans = a * b;
        } else if (op == '/') {
            ans = a / b;
        } else if (op == '^') {
            ans = (int)Math.pow(a, b);
        } else if (op == '%') {
            ans = a % b;
        }
        nums.addLast(ans);
    }
    boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

2. About advanced , In fact, it is similar to advanced equally , The focus is on maintenance priorities . But there are some coding details ：

For operators that are not single characters （ for example Function name function）, You can replace all non single character operators before processing （ take function Replace with @# etc. ）

Then make a special judgment on the special operator , Make sure you recognize the special operator during the traversal , Read it as a whole later （ Such as function(a,b) -> @(a, b),@(a, b) Treat as a whole ）

Last

This is us. 「 Brush through LeetCode」 The first of the series No.224 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases