Arithmetic Expression Evaluation

Last Updated on April 27, 2023 by Prepbytes

Arithmetic expression evaluation is the process of computing the value of a mathematical expression containing arithmetic operators, such as addition, subtraction, multiplication, and division, along with parentheses and operands. Before delving deep into the topic, let us first study what do mean by arithmetic expression in data structure.

Arithmetic Expression in Data Structure

An Arithmetic expression is a finite combination of arithmetic operands, operators(such as, +, -, /, *), and brackets. The common way of representing an arithmetic expression is by using infix notation. In infix notation, the operands are separated by an operator as shown in the below example.

For example:

 X + Y.
(X + Y) - Z.
X / Y

We can clearly see here that the two operands are always separated by an operator or a parenthesis.

The infix notation is solved using the operator precedence rule.

Operator Precedence Table

The below table shows the precedence of the operators in a sequential manner.

Example:

(4 + 5) * (8 / 4 - 2)
9 * (1 - 2)
9 * -1
-9

We can also represent an arithmetic expression using prefix or postfix notation.

Prefix Notation

In prefix notation, the operator comes first and the operands come after them. In the prefix expression, we don’t use brackets. The other name for prefix notation is Polish notation.

Example:

Prefix: +XY-MN 
Infix: (X + Y) (M – N)

Algorithm to Evaluate Prefix Notation Using Stack

Here is the step-wise algorithm for the arithmetic expression evaluation using stack in Java.

1. Read the given expression from right to left using a for loop.
2. If the current character is an operand, push it to the stack.
3. If the current character is an operator, remove the top two characters from the stack. Let’s say the removed characters are operand1 and operand2. Now. evaluate (operand1 operator operand2) and push the solution back to the stack.
4. The last character in the stack after traversing the complete prefix notation will be the solution.

Code Implementation

The code for the arithmetic expression evaluation using stack in Java fro prefix notation is given below.

import java.util.*;
public class Prepbytes
{
	public static void main(String[] args) {
		char expression[] = new char[]{'*', '-', '5', '4', '+', '3', '2'};
		int ans = evaluate(expression);
		System.out.println(ans);
	}
	
	// This function will evaluate the given expression
	public static int evaluate(char[] expression){
	    Stack<Character> st = new Stack<>();
	    int n = expression.length;
	    
	    // Traverse the given expression in left to right direction
	    for(int i = n - 1; i >= 0; i--){
	        char ch = expression[i];
	        
	        // If the current character is an operand, push it to the stack.
	        if((int)ch - '0' >= 0 && (int)ch - '0' <= 9){
	            st.push(ch);
	        }
	        
	        // If the current character is an operator.
	        else{
	            
	            // Remove the top two characters from the stack.
	            int operand2 = st.pop() - '0';
	            int operand1 = st.pop() - '0';
	            int val = 0;
	            
	            // Evaluate (operand1 operator operand2)
	            switch(ch){
	                case '+':
	                    val = operand1 + operand2;
	                    break;
                    case '-':
                        val = operand1 - operand2;
	                    break;
                    case '*':
                        val = operand1 * operand2;
	                    break;
                    case '/':
                        val = operand1 / operand2;
	                    break;
	            }
	            
	            // Push the solution back to the stack.
	            st.push((char)(val + '0'));
	        }
	    }
	    return st.pop() - '0';
	}
}

Output:

-5

Time Complexity: O(n) where n is the number of characters in the expression. Each character is pushed and popped in the stack exactly once, hence the time complexity is O(n).

Space Complexity: O(n) as we are using stack.

Postfix Notation

In postfix notation, the operators come after the operands, just opposite of the prefix notation. In the postfix expression, we don’t use brackets. The prefix notation is commonly known as Reverse Polish notation.

Example:

Prefix: NM-XY+ 
Infix: (X + Y) (M – N)

Algorithm to Evaluate Prefix Notation, Using Stack

The stepwise algorithm for arithmetic expression evaluation using stack in Java is given below.

1. Read the expression from left to right.
2. If the current character is an operand, push it to the stack.
3. If the current character is an operator, remove the top two characters from the stack. Let’s say the removed characters are operand1 and operand2. Now. evaluate (operand1 operator operand2) and push the solution back to the stack.
4. The last character in the stack after traversing the complete prefix notation will be the solution.

Dry Run for Arithmetic Expression Evaluation using Stack

Code Implementation

Here is the code implementation for the arithmetic expression evaluation using stack in Java.

import java.util.*;
public class Prepbytes
{
	public static void main(String[] args) {
		char expression[] = new char[]{'2', '3', '+', '4', '5', '-', '*'};
		int ans = evaluate(expression);
		System.out.println(ans);
	}
	
	// This function will evaluate the given expression
	public static int evaluate(char[] expression) {
	    Stack<Character> st = new Stack<>();
	    
	    // Traverse the given expression in left to right direction
	    for(char ch : expression){
	        
	        // If the current character is an operand, push it to the stack.
	        if((int)ch - '0' >= 0 && (int)ch - '0' <= 9) {
	            st.push(ch);
	        }
	        
	        // If the current character is an operator.
	        else{
	            
	            // Remove the top two characters from the stack.
	            int operand2 = st.pop() - '0';
	            int operand1 = st.pop() - '0';
	            int val = 0;
	            
	            // Evaluate (operand1 operator operand2)
	            switch(ch) {
	                case '+':
	                    val = operand1 + operand2;
	                    break;
                    case '-':
                        val = operand1 - operand2;
	                    break;
                    case '*':
                        val = operand1 * operand2;
	                    break;
                    case '/':
                        val = operand1 / operand2;
	                    break;
	            }
	            
	            // Push the solution back to the stack.
	            st.push((char)(val + '0'));
	        }
	    }
	    return st.pop() - '0';
	}
}

Output:

-5

Time Complexity: O(n) where n is the length of the expression. Each character is pushed and popped in the stack exactly once, hence the time complexity is O(n).

Space Complexity: O(n) as we are using stack.

Conclusion In this article, we learned about the arithmetic expression in data structure. We have also discussed the algorithm and code implementation of the arithmetic expression evaluation using stack in Java. Hope this blog helps you understand and solve the problem.

FAQs Related to Arithmetic Expression

Here are some frequently asked questions on arithmetic expression evaluation using stack in Java.

Ques 1. What is a stack data structure? Ans. A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. It is a collection of elements where the last element added to the stack is the first one to be removed.

Ques 2. How is a stack implemented in Java? Ans. A stack can be implemented in Java using the Stack class, which is a part of the Java Collections framework.

Ques 3. What is the difference between a stack and a queue data structure? Ans. A stack follows the Last-In-First-Out (LIFO) principle, while a queue follows the First-In-First-Out (FIFO) principle.

Ques 4. What is the postfix evaluation algorithm? Ans. The postfix evaluation algorithm is an algorithm for evaluating the value of a postfix expression using a stack data structure.