Calculator

Posted: 4 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a string 'S' of length 'N' representing an arithmetic expression. Your task is to compute the result of the expression.

For Example:
If the given arithmetic expression is: “2*3+5/6*3+15”, then the output will be 23.5.

Note:

1. The arithmetic expression consists of positive integers, +, -, *, and / (no parentheses).

2. The given input will always be a valid arithmetic expression.

3. There will be at least one integer in the given arithmetic equation.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains one integer N, as described in the problem statement.

The second line of each test case contains one string of length N, representing a valid arithmetic expression.
Output Format:
For each test case, print a single line containing a single integer representing the result of the given arithmetic equation.

The output for each test case will be printed in a separate line.

Your answer will be considered correct if its absolute or relative error doesn’t exceed 10 ^ (-6).
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= Length of the given string, N <= 30
It is guaranteed that the string will only be consisting of positive integers, +, -, * and / (no parentheses).
0 < positive integers <= 15

Time Limit: 1 sec.
Approach 1

In this approach, we will keep two different stacks, one for the operators and one for the operands. When we encounter any operand, we will push that into the operand stack. 

If we encounter any operator, we will check if the current operator has precedence greater than the previous operator or not. If the current operator has precedence lower or equal to the previous operator, then we will calculate the result for the previous operator for its operand since its priority was higher. We continue the above process till we find an operator whose precedence is smaller than the precedence of the current operator. Finally, after the whole expression is parsed, we will evaluate the remaining operators left in the stack. 

 

Steps:

 

  • Firstly we will create two empty stacks, operands, and operators.
  • We will create a function int precedence(operator) which will return the precedence of the given operator.
    • int precedence(operator):
      • If the operator is + or -, then return 1.
      • If the operator is * or /, then return 2.
  • We will create a function double evaluate(operand1, operand2, operator), which will evaluate the result for a given operator and the two operands.
  • double evaluate(operand1, operand2, operator):
    • If the operator is +, then return (operand1 + operand2)
    • If the operator is  -, then return (operand1 - operand2)
    • If the operator is  *, then return (operand1 * operand2)
    • If the operator is  /, then return (operand1 / operand2)
  • Run a loop from i = 0 to N and do:
    • If s[i] is a digit, then
      • Create a temporary variable (say temp) and initialize temp to 0. 
      • Run a while loop till i < N and s[i] is a digit:
        • temp = temp * 10 + (s[i] - '0')
        • Increment i by 1.
      • Decrement i by 1.
      • operands.push(temp)
    • else if s[i] is an operator, then
      • Run a while loop till operators is not empty AND precedence(operators.top()) >= precedence(s[i]) and do:
        • operand1 = operands.pop() and operand2 = operands.pop()
        • op = operators.pop()
        • Then call resultevaluate(operand2, operand1, op)
        • operands.push(result)
  • Run a while loop till operators is not empty and do:
    • operand1 = operands.pop() and operand2 = operands.pop()
    • op = operators.pop()
    • Then call resultevaluate(operand2, operand1, op)
    • operands.push(result)
  • Finally, return operands.top() as answer.
Try Problem