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.
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.
The below table shows the precedence of the operators in a sequential manner.
| 1) | Parentheses |
| 2) | Addition(+), Subtraction(-) |
| 3) | Multiply(*), Divide(/) |
| 4) | Relational operators(= <> < >=) |
| 5) | IS |
| 6) | NOT(~) |
| 7) | AND(&&) |
| 8) | OR(||) |
Example:
(4 + 5) * (8 / 4 - 2) 9 * (1 - 2) 9 * -1 -9We can also represent an arithmetic expression using prefix or postfix 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)Here is the step-wise algorithm for the arithmetic expression evaluation using stack in Java.
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[]; int ans = evaluate(expression); System.out.println(ans); > // This function will evaluate the given expression public static int evaluate(char[] expression) < Stackst = 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' // 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:
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.
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)The stepwise algorithm for arithmetic expression evaluation using stack in Java is given below.
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[]; int ans = evaluate(expression); System.out.println(ans); > // This function will evaluate the given expression public static int evaluate(char[] expression) < Stackst = 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' // 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:
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.
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.
