Calculator

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.

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.

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).

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.

Stack

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 result = evaluate(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 result = evaluate(operand2, operand1, op)
- operands.push(result)
Finally, return operands.top() as answer.

Time Complexity

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

Since we are iterating the given string only once, the time complexity is O(N).

Space Complexity

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

Since we are storing each operator and operands using a stack, the space complexity will be O(N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for sample input 1:

Sample Input 2:

Sample Output 2:

Explanation for sample input 2: