Arithmetic Expression Evaluation
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

Question

Arithmetic Expression Evaluation

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

Accepted Answer

1. Split the string with regex matching + sign
2. Thus, every element in the resultant String array has either a single number or an expression of products.
3. Now traverse through the array to find indices having products.
4. Split the product expression with regex matching * sign
5. Now multiply every number that was split using * sign in Step 4.
6. Finally, every index has only numbers that need to be added for the final evaluation of an expression.
7. Add integers at all indices in the array received after Step 1.
8. The sum gives the final result of the expression string.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

Time Complexity: O(n)Explanation:

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

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where ‘N’ is the length of the given string ‘expression’.

*/



#include 



bool isLowerPrecedence(char ops1, char ops2) 

{



    // Check whether ops1 has lower precedence than ops2.

    if ((ops1 == '+' || ops1 == '-') && (ops2 == '*' || ops2 == '/')) 

    {

        return true;

    }

    return false;

}



int evaluateArithmeticExpression(string & expression) 

{

    stack < char > stk;

    string postfixExp = "", operand = "";



    // Convert given infix expression to postfix/ Reverse Polish Notation.

    for (int i = 0; i < expression.length(); i++) 

    {

        if (expression[i] >= '0' && expression[i] <= '9') 

        {



            // Append digit to operand.

            operand += expression[i];

            continue;

        }



        if (operand != "") 

        {



            // Append operand in string 'postfix' 

            postfixExp += operand;

            postfixExp += ' ';

            operand = "";

        }



        if (expression[i] == '(') 

        {



            // Push opening bracket

            stk.push('(');

        } 

        

        else if (expression[i] == ')') 

        {



            // Append operators between current paranthesis pair in string postfixExp and discard paranthesis.

            while (stk.top() != '(') 

            {

                postfixExp += stk.top();

                stk.pop();

            }

            stk.pop();

        } 

        

        else 

        {

            while (stk.top() != '(' && isLowerPrecedence(expression[i], stk.top()) == false) 

            {



                // Pop operator with greater or equal precedence.

                postfixExp += stk.top();

                stk.pop();

            }



            // Add operator to top of stack.

            stk.push(expression[i]);

        }

    }



    stack < int > values;

    operand = "";



    // Evaluating equivalent postfix expression.

    for (int i = 0; i < postfixExp.length(); i++) 

    {

        if (postfixExp[i] >= '0' && postfixExp[i] <= '9') 

        {



            // Append digit to operand.

            operand += postfixExp[i];

        } 

        

        else if (postfixExp[i] == ' ') 

        {



            // Push operand in stack 'values'.

            values.push(stoi(operand));

            operand = "";

        } 

        

        else 

        {



            // Pop two operand and push their result after applying operator back to the stack 'values'.

            int operand2 = values.top();

            values.pop();

            int operand1 = values.top();

            values.pop();



            if (postfixExp[i] == '+') 

            {

                values.push(operand1 + operand2);

            }

            

            if (postfixExp[i] == '-') 

            {

                values.push(operand1 - operand2);

            }

            

            if (postfixExp[i] == '*') 

            {

                values.push(operand1 * operand2);

            }

            

            if (postfixExp[i] == '/') 

            {

                values.push(operand1 / operand2);

            }

        }

    }



    // Result of Expression

    return values.top();

}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where  ‘N’ is the length of the given string ‘expression’.

'''



def isLowerPrecedence(ops1, ops2):

    

    # Check whether ops1 has lower precedence than ops2.

    if((ops1 == '+' or ops1 == '-') and (ops2 == '*' or ops2 == '/')):

        return True



    return False





def evaluateArithmeticExpression(expression):

    stk = []



    postfixExp = ""

    operand = ""



    # Convert given infix expression to postfix/ Reverse Polish Notation.

    for i in range(len(expression)):

        if (expression[i] >= '0' and expression[i] <= '9'):

            

            # Append digit to operand.

            operand += expression[i]

            continue



        if (operand != ""):

            

            # Append operand in string 'postfix'

            postfixExp += operand

            postfixExp += ' '

            operand = ""



        if (expression[i] == '('):

            

            # Push opening bracket

            stk.append('(')

        

        elif (expression[i] == ')'):

            

            # Append operators between current paranthesis pair in string postfixExp and discard paranthesis.

            while (stk[-1] != '('):

                postfixExp += stk[-1]

                stk.pop()

            stk.pop()

        

        else:

            while (stk[-1] != '(' and isLowerPrecedence(expression[i], stk[-1]) == False):

                

                # Pop operator with greater or equal precedence.

                postfixExp += stk[-1]

                stk.pop()



            # Add operator to top of stack.

            stk.append(expression[i])



    values = []

    operand = ""



    # Evaluating equivalent postfix expression.

    for i in range(len(postfixExp)):

        if (postfixExp[i] >= '0' and postfixExp[i] <= '9'):

            

            # Append digit to operand.

            operand += postfixExp[i]

        

        elif (postfixExp[i] == ' '):

            

            # Push operand in stack 'values'.

            values.append(int(operand))

            operand = ""

        

        else:

            

            # Pop two operand and push their result after applying operator back to the stack 'values'.

            operand2 = values[-1]

            values.pop()

            operand1 = values[-1]

            values.pop()

            if (postfixExp[i] == '+'):

                values.append(operand1 + operand2)

            

            if (postfixExp[i] == '-'):

                values.append(operand1 - operand2)

            

            if (postfixExp[i] == '*'):

                values.append(operand1 * operand2)

            

            if (postfixExp[i] == '/'):

                values.append(int(operand1 / operand2))



    # Result of Expression

    return values[-1]

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where  'N' is the length of the given string 'expression'.

*/



import java.util.Stack;

import java.lang.StringBuilder;



public class Solution 

{

    public static boolean isLowerPrecedence(char ops1, char ops2) 

    {

        // Check whether ops1 has lower precedence than ops2.

        if ((ops1 == '+' || ops1 == '-') && (ops2 == '*' || ops2 == '/')) 

        {

            return true;

        }

        return false;

    }



    public static int evaluateArithmeticExpression(String expression) 

    {

        Stack stk = new Stack();



        StringBuilder postfixExp = new StringBuilder();

        StringBuilder operand = new StringBuilder();



        // Convert given infix expression to postfix/ Reverse Polish Notation.

        for (int i = 0; i < expression.length(); i++) 

        {

            if (expression.charAt(i) >= '0' &&  expression.charAt(i) <= '9') 

            {

                // Append digit to operand.

                operand.insert(operand.length(), expression.charAt(i));

                continue;

            }



            if (operand.length() != 0) 

            {

                // Append operand in string 'postfix'

                postfixExp.append(operand);

                postfixExp.insert(postfixExp.length(), ' ');

                operand.setLength(0);

            }



            if (expression.charAt(i) == '(') 

            {

                // Push opening bracket

                stk.push('(');

            } 

            

            else if (expression.charAt(i) == ')') 

            {

                // Append operators between current paranthesis pair in string postfixExp and discard paranthesis.

                while (stk.peek() != '(') 

                {

                    postfixExp.insert(postfixExp.length(), stk.peek());

                    stk.pop();

                }

                stk.pop();

            } 

            

            else 

            {

                while (stk.peek() != '(' && isLowerPrecedence(expression.charAt(i), stk.peek()) == false) 

                {

                    // Pop operator with greater or equal precedence.

                    postfixExp.insert(postfixExp.length(), stk.peek());

                    stk.pop();

                }

                // Add operator to peek of stack.

                stk.push(expression.charAt(i));

            }

        }



        Stack values = new Stack();

        operand.setLength(0);



        // Evaluating equivalent postfix expression.

        for (int i = 0; i < postfixExp.length(); i++) 

        {

            if (postfixExp.charAt(i) >= '0' && postfixExp.charAt(i) <= '9') 

            {

                // Append digit to operand.

                operand.insert(operand.length(), postfixExp.charAt(i));

            } 

            

            else if (postfixExp.charAt(i) == ' ') 

            {

                // Push operand in stack 'values'.

                values.push(Integer.valueOf(operand.toString()));

                operand.setLength(0);

            } 

            

            else 

            {

                // Pop two operand and push their result after applying operator back to the stack 'values'.

                int operand2 = values.peek();

                values.pop();

                int operand1 = values.peek();

                values.pop();



                if (postfixExp.charAt(i) == '+') 

                {

                    values.push(operand1 + operand2);

                }

                

                if (postfixExp.charAt(i) == '-') 

                {

                    values.push(operand1 - operand2);

                }

                

                if (postfixExp.charAt(i) == '*') 

                {

                    values.push(operand1 * operand2);

                }

                

                if (postfixExp.charAt(i) == '/') 

                {

                    values.push(operand1 / operand2);

                }

            }

        }



        // Result of Expression

        return values.peek();

    }

}

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 :

For example :

Input format :

Output format :

Note :

Constraints :

Top SquadStack Product Engineer interview questions & answers

Popular interview questions of Product Engineer