|
| 1 | +# 224. Basic Calculator |
| 2 | + |
| 3 | +- Difficulty: Hard. |
| 4 | +- Related Topics: Math, String, Stack, Recursion. |
| 5 | +- Similar Questions: Evaluate Reverse Polish Notation, Basic Calculator II, Different Ways to Add Parentheses, Expression Add Operators, Basic Calculator III, The Score of Students Solving Math Expression, Minimize Result by Adding Parentheses to Expression. |
| 6 | + |
| 7 | +## Problem |
| 8 | + |
| 9 | +Given a string `s` representing a valid expression, implement a basic calculator to evaluate it, and return **the result of the evaluation**. |
| 10 | + |
| 11 | +**Note:** You are **not** allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`. |
| 12 | + |
| 13 | + |
| 14 | +Example 1: |
| 15 | + |
| 16 | +``` |
| 17 | +Input: s = "1 + 1" |
| 18 | +Output: 2 |
| 19 | +``` |
| 20 | + |
| 21 | +Example 2: |
| 22 | + |
| 23 | +``` |
| 24 | +Input: s = " 2-1 + 2 " |
| 25 | +Output: 3 |
| 26 | +``` |
| 27 | + |
| 28 | +Example 3: |
| 29 | + |
| 30 | +``` |
| 31 | +Input: s = "(1+(4+5+2)-3)+(6+8)" |
| 32 | +Output: 23 |
| 33 | +``` |
| 34 | + |
| 35 | + |
| 36 | +**Constraints:** |
| 37 | + |
| 38 | + |
| 39 | + |
| 40 | +- `1 <= s.length <= 3 * 105` |
| 41 | + |
| 42 | +- `s` consists of digits, `'+'`, `'-'`, `'('`, `')'`, and `' '`. |
| 43 | + |
| 44 | +- `s` represents a valid expression. |
| 45 | + |
| 46 | +- `'+'` is **not** used as a unary operation (i.e., `"+1"` and `"+(2 + 3)"` is invalid). |
| 47 | + |
| 48 | +- `'-'` could be used as a unary operation (i.e., `"-1"` and `"-(2 + 3)"` is valid). |
| 49 | + |
| 50 | +- There will be no two consecutive operators in the input. |
| 51 | + |
| 52 | +- Every number and running calculation will fit in a signed 32-bit integer. |
| 53 | + |
| 54 | + |
| 55 | + |
| 56 | +## Solution |
| 57 | + |
| 58 | +```javascript |
| 59 | +/** |
| 60 | + * @param {string} s |
| 61 | + * @return {number} |
| 62 | + */ |
| 63 | +var calculate = function(s) { |
| 64 | + var res = 0; |
| 65 | + var i = 0; |
| 66 | + var isPlus = true; |
| 67 | + while (i < s.length) { |
| 68 | + switch (s[i]) { |
| 69 | + case ' ': |
| 70 | + i++; |
| 71 | + break; |
| 72 | + case '+': |
| 73 | + isPlus = true; |
| 74 | + i++; |
| 75 | + break; |
| 76 | + case '-': |
| 77 | + isPlus = false; |
| 78 | + i++; |
| 79 | + break; |
| 80 | + case '(': |
| 81 | + i++; |
| 82 | + var num = 0; |
| 83 | + var from = i; |
| 84 | + while (!(num === 0 && s[i] === ')')) { |
| 85 | + if (s[i] === '(') num++; |
| 86 | + if (s[i] === ')') num--; |
| 87 | + i++; |
| 88 | + } |
| 89 | + isPlus |
| 90 | + ? (res += calculate(s.slice(from, i))) |
| 91 | + : (res -= calculate(s.slice(from, i))) |
| 92 | + i++; |
| 93 | + break; |
| 94 | + default: |
| 95 | + var num = Number(s[i]); |
| 96 | + while (s[i + 1] >= '0' && s[i + 1] <= '9') { |
| 97 | + i++; |
| 98 | + num *= 10; |
| 99 | + num += Number(s[i]); |
| 100 | + } |
| 101 | + isPlus ? (res += num) : (res -= num); |
| 102 | + i++; |
| 103 | + break; |
| 104 | + } |
| 105 | + } |
| 106 | + return res; |
| 107 | +}; |
| 108 | +``` |
| 109 | + |
| 110 | +**Explain:** |
| 111 | + |
| 112 | +nope. |
| 113 | + |
| 114 | +**Complexity:** |
| 115 | + |
| 116 | +* Time complexity : O(n). |
| 117 | +* Space complexity : O(1). |
0 commit comments