Evaluate the postfix expression in java
The Postfix notation is used to represent algebraic expressions. The expressions written in postfix form are evaluated faster compared to infix notation as parenthesis are not required in postfix.
Algorithm
1. Input a postfix expression in the postfix string.
2. Declare a stack
3. for each element ß postfix
if(element is an operand) {
push element in stack
} else {
oprnd2= pop an operand from stack
oprnd1= pop an operand from stack
value = evaluate the value using operator
push value to stack
}
4. pop the top element of the stack which is the required result.
5. End
Example
String postfix = "2 3 1 * + 9 -"
| element | oprnd1 | oprnd2 | value | stack |
| 2 | | | | 2 |
| 3 | | | | 2,3 |
| 1 | | | | 2,3,1 |
| * | 3 | 1 | 3*1 | 2,3 |
| + | 3 | 2 | 3+2 | 5 |
| 9 | | | | 5,9 |
| - | 5 | 9 | 5-9 | -4 |
import java.util.Stack;
/**
* @author rajesh.dixit
*/
public class EvaluationPostfix {
public static void main(String[] args) {
String postfix = "2 3 1 * + 9 -";
String[] postfixArr = postfixArray(postfix);
int value = evaluatePostfix(postfixArr);
System.out.println("Evaluated Postfix "+ value);
}
/**
* Method to evaluate the expression.
* @param postfixArr
* @return
*/
private static int evaluatePostfix(String[] postfixArr) {
/** Declare a stack. */
Stack<Integer> stack = new Stack<Integer>();
for(String element : postfixArr) {
boolean isOperator = isOperator(element);
/* if current element is operator
* process the two operands
* else
* push the element to stack.
**/
if(isOperator) {
int value1 = stack.pop();
int value2 = stack.pop();
int calculatedValue = getCalculateValue(value2, value1, element);
stack.push(calculatedValue);
} else {
stack.push(Integer.valueOf(element));
}
}
return stack.pop();
}
/**
* Calculate the value after getting the operator.
* @param a
* @param b
* @param operator
* @return evaluated value.
*/
private static int getCalculateValue(int a, int b, String operator) {
int result = 0;
if("+".equals(operator)) {
result = (a+b);
} else if ("-".equals(operator)) {
result = (a-b);
} else if ("*".equals(operator)) {
result = (a*b);
} else if ("/".equals(operator)) {
result = (a/b);
}
return result;
}
/**
* To check whether next processed element is operator/operand.
* @param element
* @return boolean
*/
private static boolean isOperator(String element) {
if("+".equals(element) || "-".equals(element) ||
"/".equals(element) || "*".equals(element)) {
return true;
}
return false;
}
/**
* Convert the input string to array.
* @param postfix
* @return String element
*/
private static String[] postfixArray(String postfix) {
if(postfix==null || postfix.isEmpty()) {
return null;
} else {
return postfix.split(" ");
}
}
}
Output:
Evaluated Postfix -4
No comments:
Post a Comment