Skip to content

772. Basic Calculator III πŸ”’

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "1+1"
Output: 2

Example 2:

Input: s = "6-4/2"
Output: 4

Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21

 

Constraints:

  • 1 <= s <= 104
  • s consists of digits, '+', '-', '*', '/', '(', and ')'.
  • s is a valid expression.

Solutions

Solution 1

1


1


  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
118
119
120
121
122
123
class Solution {
public:
    // Define an operation function that performs mathematical operations based on the operator
    int operate(int b, char ch, int a) {
        // Note the order of ab
        switch (ch) {
        case '+':
            return a + b; // Addition
        case '-':
            return a - b; // Subtraction
        case '*':
            return a * b; // Multiplication
        case '/':
            return a / b; // Division
        default:
            break;
        }
        return 0; // Default return 0, handle invalid operators
    }

    // Calculate the value of the string expression
    int calculate(string s) {
        int preority[250]; // Operator precedence array
        preority['+'] = 1;
        preority['-'] = 1;
        preority['*'] = 2;
        preority['/'] = 2;
        preority['('] = 0;
        preority[')'] = 0;

        stack<char> op; // Operator stack
        stack<int> num; // Operand stack
        int stringsize = s.size(); // Length of the string
        int i = 0;
        char ch;

        // Traverse the string
        for (; i < stringsize; i++) {
            ch = s[i];
            if (ch == ' ') {
                continue; // Skip spaces
            }
            if (ch >= '0' && ch <= '9') {
                int realnum = ch - '0'; // Convert character to number
                // Handle multi-digit numbers
                while (s[i + 1] >= '0' && s[i + 1] <= '9') {
                    i++;
                    realnum *= 10;
                    realnum += s[i] - '0';
                }
                num.push(realnum); // Push the number onto the stack
            } else {
                // Handle operators
                if (op.empty() || ch == '(' || preority[ch] > preority[op.top()]) {
                    // Special case, handle the first character being '-' or '+'
                    if (num.empty() && (ch == '-' || ch == '+')) {
                        num.push(0);
                    }
                    op.push(ch); // Push the operator onto the stack
                    // Handle expressions inside parentheses
                    if (ch == '(') {
                        int j = i;
                        while (j + 1 < stringsize) {
                            // Preprocess the first operator inside the parentheses
                            if (s[j + 1] == '-' || s[j + 1] == '+') {
                                num.push(0);
                            }
                            if (s[j + 1] != ' ') {
                                break;
                            }
                            j++;
                        }
                    }
                } else if (ch == ')') {
                    // Handle right parentheses
                    char ch2 = ')';
                    ch2 = op.top();
                    op.pop();
                    while (ch2 != '(') {
                        int a = num.top();
                        num.pop();
                        int b = num.top();
                        num.pop();
                        num