Arithmetic Expression Evaluation

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
24 upvotes
Asked in companies
AdobeFacebookMicrosoft

Problem statement

You are given a string ‘expression’ consists of characters ‘+’, ‘-’, ‘*’, ‘/’, ‘(‘, ‘)’ and ‘0’ to ‘9’, that represents an Arithmetic Expression in Infix Notation. Your task is to evaluate this Arithmetic Expression.

In Infix Notation, operators are written in-between their operands.

Note : 
1. We consider the ‘/’ operator as the floor division.

2. Operators ‘*’ and ‘/’ expression has higher precedence over operators‘+’ and ‘-’ 

3. String expression always starts with ‘(‘ and ends with ‘)’.

4. It is guaranteed that ‘expression’ represents’ a valid expression in Infix notation.

5. It is guaranteed that there will be no case that requires division by 0.

6. No characters other than those mentioned above are present in the string. 

7. It is guaranteed that the operands and final result will fit in a 32-bit integer.
For example : 
Consider string ‘expression’ = ‘((2+3)*(5/2))’. 
Then it’s value after evaluation will be ((5)*(2)) = 10.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next T lines represent the ‘T’ test cases.

The first and only line of each test case contains the string ‘expression’.
Output format : 
For each test case, in a separate line print an integer representing the value of the given arithmetic expression after evaluation.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
3 <= |expression| <= 10^4

Time limit: 1 sec
Sample Input 1 :
2
(2)
((2+3)*(5/2))
Sample Output 1 :
2
10
Explanation For Sample Input 1 :
Test case 1 :
The value of the expression “(2)” will be 2 after evaluation.

Test case 2 :
See the problem statement for an explanation.
Sample Input 2 :
2
(121+(101+0))
(3*(5+2)*(10-7))
Sample Output 2 :
222
63
Hint

Convert the given expression into  Reverse Polish Notation (Postfix Expression).

Approaches (1)
Reverse Polish Notation

Infix Expressions are harder for Computers to evaluate because of the additional work needed to decide precedence, so we first convert infix expressions into either postfix or prefix expressions.  In this approach, we convert Infix expression into Postfix expression also known as Reverse Polish Notation, and then evaluate the postfix expression using stack.  Note in postfix expression, the operator is followed for every pair of operands.

 

For example, If the infix expression is (2+3) then its postfix expression will be 2 3+, we will use a single space to denote the end of one operand in the postfix expression.

 

Algorithm

 

  • Create an empty string ‘postfixExp’ and an empty stack of character ‘stk’.
  • Create another string operand.
  • Iterate over the given string from left to right and for each character do the following.
    • If the current character is between ‘0’ to ‘9’ then append it in the string operand and continue.
    • Otherwise, if the current character is operator or bracket, then first append operand + single space to ‘postfixExp’  and make string operand empty. 
    • If the current character is ‘(‘ then push it to the stack ‘stk’.
    • If the current character is ‘)’, then repeatedly pop the stack and append them to  ‘postfixExp’ until the top character is not ‘(‘. Discard both parentheses after it.
    • If the current character is the operator i.e (‘+’, ‘-’, ‘*’, ‘/’) then repeatedly pop all the operators from the top of the stack whose precedence is greater or equal to it and append them to‘postfixExp’, If no such operator is at the top of the stack, then push it in the stack.
  • String ‘postfixExp’ now has a postfix expression for the given string, now we can easily evaluate it using stack.
  • Create a stack of integers, let’s name it ‘values’.
  • Iterate over ‘postfixExp’ from left to right,  if the current character is between 0 to 9, then append it to the string operand, otherwise, if the current character is space then append its equivalent integer to ‘values’ and make string operand empty. If  the current character is an operator then pop two elements from the top of the stack apply this operator between then and push back the result
  • Only one integer left in stack ‘values’, Return it, as it will be the required result.

 

We can alternatively convert the expression in prefix notation and then evaluate it, the approach will be similar to this one.

Time Complexity

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

 

Push and pop operation in stack takes O(1) time. Here we iterate over the string ‘expression’ and ‘postfixExp’ and perform pop and push operations in the stack in each iteration. The length of both strings is of the order of ‘N’, thus the number of push and pop operations on the stack is also the order of ‘N’. So, the overall complexity will be O(N).

Space Complexity

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

 

The extra space is used by stacks and string ‘postfixExp’, both of them have a size of the order of ‘N’. Thus, overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Arithmetic Expression Evaluation
Full screen
Console