Basic Calculator Iii - Leetcode Solution

Problem Statement:

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators , 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].

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: expression = "(2+6* 3+5- (3*14/7+2)*5)+3" Output: -12

Approach:

In order to solve this problem, first, we need to identify the different operators and their priorities. There are two types of operators, Unary and Binary operators.

Unary Operators include + and – for positive and negative values, respectively. It can act as a prefix or postfix operator for a number.

Binary Operators include +, -, *, and / along with brackets () to indicate precedence.

We can use a stack to keep track of the result so far. We push the sign of the next number we encounter on the stack, and then we push the number itself onto the stack.

When we encounter a closing bracket, we pop the stack until we encounter the corresponding opening bracket. Then we evaluate the expression on the stack and push the result onto the stack again.

We can then evaluate the entire expression on the stack and return the final result.

Let's implement the solution step-by-step:

Step 1: Initialize a stack to keep track of the result so far.

Step 2: Initialize variables to keep track of the current value, the sign of the current value, and the result.

Step 3: Loop through all the characters in the expression.

Step 4: If the current character is a digit, we add it to the current value.

Step 5: If the current character is an operator or the last character, we perform the appropriate operation based on the previous operator.

Step 6: If the current character is an opening bracket, we push the current value and the sign onto the stack and set the current value and sign to 0 and +, respectively.

Step 7: If the current character is a closing bracket, we evaluate the expression on the stack and push the result onto the stack again.

Step 8: After the loop, we evaluate the entire expression on the stack and return the final result.

Solution:

class Solution { public: int calculate(string s) { stack<int> st; int res = 0; int cur = 0; int sign = 1; int n = s.size(); for(int i=0; i<n; i++){ char c = s[i]; if(isdigit(c)){ cur = cur10+(c-'0'); } else if(c=='+' || c=='-' || c=='' || c=='/' || i==n-1){ if(c=='+' || c=='-'){ res += signcur; cur = 0; sign = (c=='+') ? 1 : -1; } else if(c=='' || c=='/'){ int a = cur; i++; while(s[i]==' ') i++; char d = s[i]; i++; while(s[i]==' ') i++; int b = 0; while(i<n && isdigit(s[i])){ b = b10+(s[i]-'0'); i++; } i--; if(d==''){ cur = ab; } else{ cur = a/b; } } else{ res += signcur; cur = 0; if(st.top()==-1){ st.pop(); sign = -1; } else{ sign=1; } int val = st.top(); st.pop(); res = val + signres; } } else if(c =='('){ st.push(res); if(sign==-1){ st.push(-1); sign = 1; } st.push(sign); res = 0; cur =0; sign = 1; } else if(c==')'){ res += signcur; cur = 0; if(st.top()==-1){ st.pop(); sign = -1; } else{ sign = 1; } int val = st.top(); st.pop(); res = val + sign*res; } } return res; } };

Time Complexity: O(n), where n is the length of the expression.

Space Complexity: O(n), we use a stack to keep track of intermediate results.

1