Sample Code to Evaluate an Infix Expression

Following is some sample code to demonstrate converting an infix expression to postfix and to evaluate the postfix expression. This was written in response to a query posted on the Webmaster Talk forum. This type of thing seems to pop-up quite frequently so, I figured I'd go ahead and post a solution.

The source is available for this file. I have also prepared a jUnit test to demonstrate the usage of this class.

Please note that this is a pretty simple example. It also only processes integer values. Changing this is pretty simple. If it can't be discovered by reading the code, a quick google will point you to the algorithimic changes.

There's also a very good article at IBM Developerworks that goes into more detail and describes some alternative techniques.

A for licensing, just consider this public domain. The algorithm is long well established. Implementations will vary very little anyway.

package com.willcode4beer.demo.infix;

import java.util.Stack;

/**
 * Class to evaluate infix and postfix expressions.
 * 
 * @author Paul E. Davis (feedback@willcode4beer.com)
 */
public class InfixPostfixEvaluator {

	/**
	 * Operators in reverse order of precedence.
	 */
	private static final String operators = "-+/*";
	private static final String operands = "0123456789";

	public int evalInfix(String infix) {
		return evaluatePostfix(convert2Postfix(infix));
	}

	public String convert2Postfix(String infixExpr) {
		char[] chars = infixExpr.toCharArray();
		Stack&lt;Character&gt; stack = new Stack&lt;Character&gt;();
		StringBuilder out = new StringBuilder(infixExpr.length());

		for (char c : chars) {
			if (isOperator(c)) {
				while (!stack.isEmpty() && stack.peek() != '(') {
					if (operatorGreaterOrEqual(stack.peek(), c)) {
						out.append(stack.pop());
					} else {
						break;
					}
				}
				stack.push(c);
			} else if (c == '(') {
				stack.push(c);
			} else if (c == ')') {
				while (!stack.isEmpty() && stack.peek() != '(') {
					out.append(stack.pop());
				}
				if (!stack.isEmpty()) {
					stack.pop();
				}
			} else if (isOperand(c)) {
				out.append(c);
			}
		}
		while (!stack.empty()) {
			out.append(stack.pop());
		}
		return out.toString();
	}

	public int evaluatePostfix(String postfixExpr) {
		char[] chars = postfixExpr.toCharArray();
		Stack&lt;Integer&gt; stack = new Stack&lt;Integer&gt;();
		for (char c : chars) {
			if (isOperand(c)) {
				stack.push(c - '0'); // convert char to int val
			} else if (isOperator(c)) {
				int op1 = stack.pop();
				int op2 = stack.pop();
				int result;
				switch (c) {
				case '*':
					result = op1 * op2;
					stack.push(result);
					break;
				case '/':
					result = op2 / op1;
					stack.push(result);
					break;
				case '+':
					result = op1 + op2;
					stack.push(result);
					break;
				case '-':
					result = op2 - op1;
					stack.push(result);
					break;
				}
			}
		}
		return stack.pop();
	}
	private int getPrecedence(char operator) {
		int ret = 0;
		if (operator == '-' || operator == '+') {
			ret = 1;
		} else if (operator == '*' || operator == '/') {
			ret = 2;
		}
		return ret;
	}
	private boolean operatorGreaterOrEqual(char op1, char op2) {
		return getPrecedence(op1) &gt;= getPrecedence(op2);
	}

	private boolean isOperator(char val) {
		return operators.indexOf(val) &gt;= 0;
	}

	private boolean isOperand(char val) {
		return operands.indexOf(val) &gt;= 0;
	}

}