Last Updated: 15 Feb, 2021
Arithmetic Expression Evaluation
Moderate
Asked in companies
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.
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
Approaches
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.