This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021″

1, the title

Given a string expression s, you implement a basic calculator to evaluate and return its value.

Integer division preserves only integer parts.

Example 1:

Input: s = "3+2*2" Output: 7Copy the code

Example 2:

Input: s = "3/2" Output: 1Copy the code

Example 3:

Input: s = "3+ 5/2" Output: 5Copy the code

Tip:

  • 1 <= s.length <= 3 * 105
  • sIntegers and operators(' + ', '-', '*', '/')Is separated by some Spaces
  • sSaid aValid expression
  • All integers in the expression are non-negative integers and are in range[0, 2 ^ 31-1) 内
  • The problem data guarantees that the answer is a 32-bit integer

2, train of thought

O(n)O(n)O(n)

For expression evaluation problems, we maintain two stacks, a num stack for recording numbers and an op stack for recording operators, iterating through expressions and evaluating numbers when operators are encountered.

First, we define an eval() function, which is used to pop two numbers a and B from the numeral stack num, and then pop the operation symbol from the operator stack op. After calculation, we add the result number to num.

Specific definitions are as follows:

void eval(a) 
{
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int r;
    if (c == '+') r = a + b;
    else if (c == The '-') r = a - b;
    else if (c == The '*') r = a * b;
    else r = a / b;
    num.push(r);
}
Copy the code

Then we scan the entire expression from front to back:

  • 1, skip when a space ‘ ‘is encountered.

  • 2. When a number is encountered, a contiguous full number is read and added to num.

  • When using the ‘+’, ‘-‘, ‘*’, ‘/’ operators, we need to consider the precedence:

    • If the operator stackopThe top of the stack element has a higher priority than the currently encountered operatorwhileCycle areeval()Operation, namely number stacknumThe two elements at the top of the stack are taken out, and then the stack is combined with the operatoropThe top of the stack operator performs the corresponding calculation and pushes the calculation result back onto the numeric stacknumIn the.
    • Otherwise, the current operator is pushed onto the operator stackopIn the.

  • 4. After scanning the entire expression, if there are still elements in the operator stack op, the while loop evaluates ().

  • 5, return num at the top of stack.

Diagram process:

Details:

  • 1. Since the operators have precedence, design a hash table to store them'+'.The '-'.The '*'.'/'Priority, we will'+'andThe '-'Set to1Priority Indicates the priority of theThe '*'and'/'Set to2Level Indicates the priority.
  • 2. Consider the expressionsThe first number of PI could be negative, so we givesAdd a character at the beginning0.

Time complexity analysis: Each number and operation goes on and off the stack once, so the total time complexity is O(n)O(n)O(n).

C++ code

class Solution {
public:
    stack<int> num;  // Store numbers
    stack<char> op;  // Store operation

    void eval(a) 
    {
        int b = num.top(); num.pop();
        int a = num.top(); num.pop();
        char c = op.top(); op.pop();
        int r;
        if (c == '+') r = a + b;
        else if (c == The '-') r = a - b;
        else if (c == The '*') r = a * b;
        else r = a / b;
        num.push(r);
    }

    int calculate(string s) {
        s = '0' + s;  // Start with a negative number
        unordered_map<char.int> pr; 
        pr['+'] = pr[The '-'] = 1, pr[The '*'] = pr['/'] = 2; // Define the priority of the operator
        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i]; 
            if(c == ' ') continue;  // Skip the space
            if(isdigit(c))     //c is a number, read a consecutive number
            {
                int x = 0, j = i;
                while(j < s.size() && isdigit(s[j])) x = x * 10 + (s[j++] - '0');
                num.push(x);    // Add to the stack
                i = j - 1;        
            }
            else  //c is the operator
            {     // if the stack is not empty and the priority of the top operator is greater than or equal to the priority of the current operator c, eval() is performed
                while(op.size() && pr[op.top()] >= pr[c]) eval(); op.push(c); }}while(op.size()) eval(); 
        returnnum.top(); }};Copy the code

4. Java code

class Solution {
    static Stack<Integer> num = new Stack<Integer>();
    static Stack<Character> op = new Stack<Character>();
    static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    static void eval(a)
    {
        int b = num.pop();
        int a = num.pop();
        char c = op.pop();
        int r = 0;
        if(c == '+') r = a + b;
        else if(c == The '-') r = a - b;
        else if(c == The '*') r = a * b;
        else r = a / b;
        num.add(r); 
    }
    public int calculate(String s) {
        s = '0' + s; // Start with a negative number
        map.put('+'.1);   // Define the priority of the operator
        map.put(The '-'.1);
        map.put(The '*'.2);
        map.put('/'.2);
        for(int i = 0; i < s.length(); i ++) {char c = s.charAt(i);
            if(c == ' ') continue;  // Skip the space
            if(c >= '0' && c <= '9')  //c is a number, read a consecutive number
            {
                int x = 0, j = i;
                while(j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9')
                {
                    x = x * 10 + s.charAt(j) - '0';
                    j ++;
                }
                i = j - 1;
                num.add(x);
            }
            else  //c is the operator
            {     // if the stack is not empty and the priority of the top operator is greater than or equal to the priority of the current operator c, eval() is performed
                while(!op.isEmpty() && map.get(op.peek()) >= map.get(c)) eval();
                op.add(c); 
            }
        }
        while(! op.isEmpty()) eval();returnnum.pop(); }}Copy the code

Original link: 227. Basic Calculator II