Tag Archives: data structure

Evaluation of postfix expression

This post deals with the evaluation of postfix expression also known as reverse polish notation. Please refer to the wikipedia page for the details like advantages and examples. The algorithm essentially is:postfix

  • While there are input tokens left
    • Read the next token from input.
    • If the token is a value
      • Push it onto the stack.
    • Otherwise, the token is an operator (operator here includes both operators and functions).
      • It is known in advance that the operator takes n arguments.
      • If there are fewer than n values on the stack
        • (Error) The user has not input sufficient values in the expression.
      • Else, Pop the top n values from the stack.
      • Evaluate the operator, with the values as arguments.
      • Push the returned results, if any, back onto the stack.
  • If there is only one value in the stack
    • That value is the result of the calculation.
  • Otherwise, there are more values in the stack
    • (Error) The user input has too many values.

The Java program implementing the above algorithm for evaluation of postfix expression is as follows:

class Stack {
    class OverflowException extends RuntimeException {
	public OverflowException() {
	    super("Overflow: No memory left");
	} 
	public String toString() {
	    return "OverflowException: No memory left";
    	}
    } 
    class UnderflowException extends RuntimeException {
		public UnderflowException() {
			super("Underflow: No node left");
		} 
		public String toString() {
			return "UnderflowException: No node left";
		}
    }
    class Node {
		float data;
		Node next;
		public Node(float data) {
			this.data = data;
		}
    } 
    private Node top;
    public Stack() {
		top = null;
    }
    public boolean isEmpty() {
		return top == null;
    }
    public void push(float data) {
		try {
			Node newNode = new Node(data);
			newNode.next = top;
			top = newNode;
		} catch(OutOfMemoryError e) {
			throw new OverflowException();
		}
    }
    public float pop() {
		if (isEmpty()) throw new UnderflowException();
		float data = top.data;
		top = top.next;
		return data;
    }
}

class Expression {
	public static boolean isOperator( String part ){
		if( part.length() == 1){
			char ch=part.charAt(0);
			if(ch=='+' || ch == '-' || ch == '/' || ch == '*' ) return true;
		}
		return false;
	}
    public static float evaluatePostFixExpression(String expr) {
	String part[] = expr.split(" ");
	float ans = 0f, result = 0;;
	float op1, op2;
	Stack stkOpr = new Stack();
	for (int i = 0; i < part.length; i++) {
	    System.out.println(part[i]);
	    if ( isOperator(part[i])) {
			op2 = stkOpr.pop();
			op1 = stkOpr.pop();
			if (part[i].charAt(0) == '+') {
				result = op1 + op2;
			}else if (part[i].charAt(0) == '-') {
				result = op1 - op2;
			}else if (part[i].charAt(0) == '/') {
				result = op1 / op2;
			}else if (part[i].charAt(0) == '*') {
				result = op1 * op2;
			}
			stkOpr.push(result);
		} else {
			stkOpr.push(Float.parseFloat(part[i]));
		}
	}
	ans = stkOpr.pop();
	if (!stkOpr.isEmpty()) throw new IllegalArgumentException();
	return ans;
    }
    public static void main(String args[]) {
		System.out.println(evaluatePostFixExpression("3 2 + 5 /"));
    }
}

Please refer to my earlier article Stack in Java for the details of the implementation of a Stack. Please note that in the Stack class given above the data part is of float type. This has been done because we may get a fractional value due to the presence of a division (/) operator in the input string. Also note that we are assuming that the input string does not contain characters other than the four operators and numerals.

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.