We are given an algebraic expression string `s` and we need to return the evaluated result. \n\n---\n\n\u2714\uFE0F ***Solution - I (Convert to Postfix & Evaluate)***\n\nWe use postfix/prefix notation because they are easier to parse and evalute. So, we can convert the given infix notation to postfix and then evaluate the postfix expression. Both are standard algorithm.\n\nTo convert into postfix notation -\n* Initialize an empty stack and iterate over the given expression string\n* if character is digit, then add it to postfix string\n* If character is operator, pop from stack and add to postfix string till precedence of stack top is greater or equal to current operator (this ensures higher precedence operator are evaluated first). Then push the current operator to stack\n* Finally pop all remaining operators from stack and add to postfix string\n\nWe also use separator (`\'|\'` in below code) after each number to help distinguish between start and end of a number. For eg If we have `12 + 34`, the postfix expression is `1234+` but to help separate original numbers, we make it as `12|34|+`.\n\nThen we evaluate postfix string as -\n* Initialize an empty stack and iterate over the postfix string\n* If character is digit, form the complete number and push it into stack\n* If character is operator, pop top two numbers from stack, evaluate using the current operator and push the result back into stack.\n* Finally, only one number will be present in stack which will be final result\n\n**C++**\n```cpp\nclass Solution {\npublic:\n string toPostfix(string& s) {\n auto precedence = [](char c){return c == \'*\' || c == \'/\';};\n stack op;\n string post = "";\n for(auto c : s) \n if(c == \' \') continue;\n else if(isdigit(c)) post += c;\n else {\n post += \'|\'; // markers to separate numbers\n while(size(op) && precedence(c) <= precedence(op.top())) \n post += op.top(), op.pop();\n op.push(c);\n }\n \n post += \'|\';\n while(size(op)) \n post += op.top(), op.pop(); \n return post;\n }\n int calculate(string& s) {\n s = toPostfix(s);\n stack num;\n for(int i = 0; i < size(s); i++) \n if(isdigit(s[i])) {\n int cur = 0;\n while(i < size(s) && isdigit(s[i]))\n cur = cur * 10 + (s[i++] - \'0\');\n num.push(cur);\n }\n else {\n int num1 = num.top(); num.pop();\n int num2 = num.top(); num.pop();\n if(s[i] == \'*\') num.push(num2 * num1);\n else if(s[i] == \'/\') num.push(num2 / num1);\n else if(s[i] == \'+\') num.push(num2 + num1);\n else if(s[i] == \'-\') num.push(num2 - num1);\n }\n \n return num.top();\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def calculate(self, s):\n def precedence(c):\n return c == \'*\' or c == \'/\'\n def toPostfix(s):\n op, post = deque(), \'\'\n for c in s:\n if c == \' \': continue\n elif c.isdigit(): post += c\n else:\n post += \'|\'\n while op and precedence(c) <= precedence(op[-1]):\n post += op.pop()\n op.append(c)\n \n return post + \'|\' + \'\'.join(reversed(op))\n \n s, num, i = toPostfix(s), deque(), 0\n while i < len(s):\n if s[i].isdigit():\n j = s.find(\'|\', i+1)\n num.append(int(s[i:j]))\n i = j\n else:\n num1, num2 = num.pop(), num.pop()\n if s[i] == \'*\': num.append(num2 * num1)\n elif s[i] == \'/\': num.append(num2 // num1)\n elif s[i] == \'+\': num.append(num2 + num1)\n elif s[i] == \'-\': num.append(num2 - num1)\n i += 1\n\n return num.pop()\n \n```\n\n***Time Complexity :*** `O(N)`, where `N` is the length of input string. We need `O(N)` to convert it to postfix and another `O(N)` time to evaluate the postfix string.\n***Space Complexity :*** `O(N)`, required for converting to postfix\n\n---\n\n\u2714\uFE0F ***Solution - II (Inplace Evaluation)***\n\nWe can also do the evaluation inplace with approach similar to previous solution but without explicitly converting the given string to postfix string. \n\nIn this approach, we will maintain two separate stacks, one to store operators `op` one to store numbers `num`. \n* If we get a digit, we will form complete number and push it into `num` stack\n* If we get an operator, we pop previous operators of greater or equal precedence from `op` stack, evaluate it on top two numbers from `num` stack and push the result back into `num` stack. Finally, we push the current operator into `op` for later evaluation.\n* Lastly, we will be left with the last number. We push it into `num` stack and evaluate remaining operators from `op` till it isnt empty.\n\nThis approach is just combination of above solution\'s logic but evaluates it directly without converting to postfix.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int calculate(string& s) {\n auto precedence = [](char c){return c == \'*\' || c == \'/\';};\n stack op;\n\t\tstack num;\n int cur = 0;\n s += \'#\'; // ensures all processing happens in loop...else we need to write an condition outside to take care of last number \n for(auto c : s) \n if(c == \' \') continue;\n else if(isdigit(c)) \n cur = cur * 10 + (c-\'0\'); \n else {\n num.push(cur); // push the number formed till now \n while(size(op) && precedence(c) <= precedence(op.top())) { // evaluate operators in stack having precedence >= current operator\n int num1 = num.top(); num.pop();\n int num2 = num.top(); num.pop();\n char curOp = op.top(); op.pop();\n\n if(curOp == \'*\') num.push(num2 * num1);\n else if(curOp == \'/\') num.push(num2 / num1);\n else if(curOp == \'+\') num.push(num2 + num1);\n else if(curOp == \'-\') num.push(num2 - num1);\n } \n op.push(c); // push current operator to evaluate later\n\t\t\t\tcur = 0; // reset the number\n }\n \n return num.top();\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def calculate(self, s):\n def precedence(c):\n return c == \'*\' or c == \'/\'\n\n op, num, cur = deque(), deque(), 0\n for c in s + \'#\':\n if c == \' \': continue\n elif c.isdigit():\n cur = cur * 10 + int(c)\n else:\n num.append(cur)\n while op and precedence(c) <= precedence(op[-1]):\n num1, num2, curOp = num.pop(), num.pop(), op.pop()\n if curOp == \'*\': num.append(num2 * num1)\n elif curOp == \'/\': num.append(num2 // num1)\n elif curOp == \'+\': num.append(num2 + num1)\n elif curOp == \'-\': num.append(num2 - num1)\n op.append(c)\n cur = 0\n \n return num.pop()\n```\n\n***Time Complexity :*** `O(N)`, we are iterating over the string only once\n***Space Complexity :*** `O(1)`, it might seem `O(N)` at first but analyzing the code, we can see that the number of elements in either `op` stack never exceeds two. This is because the expression is simple and doesnt contain any brackets to further determine precedence amongst terms. Thus, we append an operator without popping only when precedence of current character > stack\'s top character. This happens consecutively atmost twice (once when stack is empty and next when precedence of current operator is greater than stack top operator) and thus `op` stack\'s size will never grow beyond 2. Similarly, the `num` stack\'s size will never grow beyond 3.\n\n---\n\n\u2714\uFE0F ***Solution - III (Without Stack)***\n\nWe can solve it without any postfix logic by observing a pattern in our evaluation. First thing to observe is that we are only evaluating previous seen operator and not the current operator since we would need to know the next number as well before we can evaluate the term using current operator.\n\nNow, if the previous operator was `*` or `/`, we can directly evaluate the term. Eg. If we have `a * b + ...`, `a * b / ...` or `a * b - ...`, we can always evaluate the term `a * b` without caring what next term would be. Same thing if it was `a / b`. (Note that `a` can be individual term or intermediate result formed by cumulative result of previous `* & /` operations...it is denoted by `interimRes` in below code)\n\nHowever, if the previous operator was `+` or `-`, the evaluation depends on current operator. For eg. In `a + b - ...`, we can evaluate `a + b` and we would get correct result in both cases. But in `a + b * ...`, evaluating `a + b` would give wrong result. Same thing if it was `a - b`. \nSo, if current operator is `* or /`, then we need to add `a` to the final result and later add result of remaining expression later. If current operator is `+ or -`, we can either do the same thing by adding `a` to final result or evaluate `a + b` term & add to result. But to decouple the case from current operator and to generalize the case, in both cases, we will only add `a` to the final result & later add result of remaining expression.\n\nSo, we have following cases -\n1. **previous operator was `*` or `/`**:\n\t* Directly evaluate 1st term - `a * b` or `a / b`. This is denoted as `interimRes *= cur` or `interimRes /= cur` in below code)\n\t* Maintain `interimRes` as we may need it if future operators are `*` or `/` as well.\n2. **previous operator was `+` or `-`**: \n\t* Add `a` to final result and later we will add the result of remaining expression. Thus, in below code, we first add `interimRes` to final `ans`. \n\t* Then, update `interimRes` to hold remaining expression found till now, i.e, `\xB1cur` depending on `prevOp`.\n\t\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int calculate(string& s) {\n int cur = 0, ans = 0, interimRes = 0;\n char prevOp = \'+\';\n s += "##"; // just ensures all processing happens in loop...else we need to write outside for the last number\n for(auto c : s)\n if(c == \' \') continue;\n else if(isdigit(c)) \n cur = cur * 10 + (c-\'0\');\n else {\n if(prevOp == \'*\') // \'*\': Case-1\n interimRes *= cur;\n else if(prevOp == \'/\') // \'/\': Case-1\n interimRes /= cur;\n else // \'+\' and \'-\': Case-2\n ans += interimRes,\n interimRes = prevOp == \'+\' ? cur : -cur;\n prevOp = c;\n cur = 0;\n }\n\n return ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def calculate(self, s):\n cur, ans, interimRes, prevOp = 0, 0, 0, \'+\'\n for c in s + \'##\':\n if c == \' \': continue\n elif c.isdigit():\n cur = cur * 10 + int(c)\n else:\n if prevOp == \'*\': interimRes *= cur\n elif prevOp == \'/\': interimRes = trunc(interimRes / cur)\n else:\n ans += interimRes\n interimRes = cur if prevOp == \'+\' else -cur\n prevOp, cur = c, 0\n return ans\n```\n\n***Time Complexity :*** `O(N)`\n***Space Complexity :*** `O(1)`\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---

Basic Calculator II

Problem Description

Problem Description

Answer Panel