Last Updated: 25 Aug, 2021

Basic Calculator Il

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In the previous approach, we used a stack to track the values of the evaluated expressions. In the end, we delete all the values from the stack and add them to the result. Instead of that, we could add the values to the result beforehand and keep track of the last calculated number, thus eliminating the need for the stack.

Algorithm :

Take a variable ‘length’ and initialize it to the length of STR.
If ‘length’ is equal to 0 then return 0.
Take a variable ‘currentNumber’, ‘lastNumber,’ and ‘result’ initialize all to 0.
Take a variable ‘sign’ and initialize it to ‘+’.
Iterate ‘i’ from 0 to length - 1:
- Take a variable ‘currentChar’ and initialize it with STR[i].
- If ‘currentChar’ is digit
  - Store (‘currentNumber’ * 10) + (‘currentChar’ - '0') in ‘currentNumber’.
- If ‘currentChar’ is not digit or ‘i’ is equal to ‘length’ - 1:
  - If ‘sign’ is equal to ‘+’ or sign is equal to ‘-’
    - Increment ‘result’ by ‘lastNumber’.
    - If ‘sign’ is equal to ‘+’
      - Store ‘currentNumber ‘ in ‘lastNumber’.
    - Otherwise
      - Store -1 * ‘currentNumber’ in ‘lastNumber.
  - if ‘sign’ is equal to ‘*’
    - Store ‘lastNumber’ * ‘currentNumber’ in ‘lastNumber’.
  - if ‘sign’ is equal to ‘/’
    - ‘Store ‘lastNumber’ / ‘currentNumber’ in ‘lastNumber’.
  - Store ‘currentChar’ in ‘sign’.
  - Make ‘currentNumber’ equal to 0.
Increment ‘result’ by ‘lastNumber’.
Return ‘result’.

Solve now