Basic Calculator Il

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in companies
MicrosoftAmazonNextech

Problem statement

You are given a string ‘STR’, which represents an expression. Your task is to evaluate the value of the expression. The integer division should truncate toward zero.

For Example: 
Consider STR = “3+2*2”
Using the BODMAS rule, the expression after evaluation gives 7. Hence, the answer is 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains a string ‘STR’, which represents the given expression.
Output Format: 
For each test case, print a single integer representing the value of the given expression.

The output of each test case will be printed on a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= |STR| <= 10 ^ 6

‘STR’ consists of integers and operators (+, -, \, *).
‘STR’ represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 10 ^ 8].

Time Limit: 1 sec.
Note : 
The evaluated string is always less than or equal to 10 ^ 9.
Sample Input 1:
2
3+2*2
3+5/2
Sample Output 1:
7
5
Explanation of Sample Input 1:
In the first test case, using the BODMAS rule, the expression after evaluation gives 7. Hence, the answer is 7.

In the second test case, using the BODMAS rule, the expression after evaluation gives 5. Hence, the answer is 5.
Sample Input 2:
2
3/2
2+2/2
Sample Output 2:
1
3
Hint

Can you solve it using a stack?

Approaches (2)
Using Stack

Scan the input string ’STR’ from left to right and evaluate the expressions based on the following rules:

  • We will maintain a variable ‘currentNumber’  to store the number. If the current character is a digit [0 - 9] ( operand ), add it to ‘currentNumber’.
  • Otherwise, the current character must be an operation(+, -, *, /). Evaluate the expression based on the type of operation.
  • Addition (+) or Subtraction (-) We must evaluate the expression later based on the next operation. So, we must store the currentNumber to be used later. We will Insert the currentNumber in the Stack.

 

Algorithm :

 

The steps are as follows:

  • Maintain a variable ‘length’ and initialize it to the length of ‘STR’.
  • If ‘length’ is equal to 0 then return 0.
  • Take a ‘stack’ of integer type.
  • Take a variable ‘currentNumber’, initialize it to 0.
  • Take a variable ‘operation’, initialize it to ‘+’.
  • Iterate ‘i’ from 0 to ‘length’ - 1”
    • Take a variable ‘currentChar’ and initialize it to STR[i].
    • If ‘currentChar’ is digit
      • Store (‘currentNumber’ * 10) + (‘currentChar’ - '0') in ‘currentNumber’.
    • If ‘currChar’ is not digit or ‘i’ is equal to ‘length’ - 1:
      • If ‘operation’ is equal to ‘-’
        • Insert  -1 * ‘currentNumber’ into ‘stack’.
      • Else If ‘operation’ is equal to ‘+’
        • Insert  ‘currentNumber’ into ‘stack.
      • Else If ‘operation’ is equal to ‘*’
        • Store stack top in  ‘stackTop’.
        • Remove stack top.
        • Insert ‘stackTop’ * ‘currentNumber’ in the stack.
      • Else If ‘operation’ is equal to ‘/’
        • Insert stack top in  ‘stackTop’.
        • Remove stack top.
        • Insert ‘stackTop’ / ‘currentNumber’ in stack.
      • Store ‘currentChar’ in ‘operation’.
      • Make ‘currentNumber’ equal to 0.
  • Maintain a variable ‘result’ and initialize it to zero.
  • Iterate while the stack is not empty
    • Increment ‘result’ by the top element of the stack.
    • Remove the top element from the stack.
  • Return result.
Time Complexity

O(N), where ‘N’ is the length of the string.

 

 We will iterate over the string ‘STR’ at most twice to evaluate the string. Hence the overall time complexity is O(N).

Space Complexity

 O(N), where ‘N’ is the length of the string.

 

In the worst case, the stack requires O(N) space complexity. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Basic Calculator Il
Full screen
Console