weiss$ java DelimiterCheckerApp 
a -> true
(a) -> true
[a] -> true
{a} -> true
 true
([a]) -> true
(a] -> false
)a( -> false
 -> true
 

weiss$ java DelimiterCheckerApp "{a + (b)}"
{a + (b)} -> true

An Exception-Oriented Implementation

import java.util.Stack;

class DelimiterChecker {
	static void check(String exp) throws DelimiterCheckerException {
		Stack<Character> stack = new Stack<>();
		for (char c : exp.toCharArray()) {
			if (isOpener(c))
				stack.push(c);
			else if (isCloser(c)) {
				if (stack.empty()) throw new DelimiterCheckerException("Missing opener");
				char opener = stack.pop();
				if (!matches(opener, c)) throw new DelimiterCheckerException("Mismatched delimiters");
			}
		}

		if (!stack.empty()) throw new DelimiterCheckerException("Missing closer(s)");
	}

	private static boolean isOpener(char c) {return OPENERS.indexOf(c) >= 0;}
	private static boolean isCloser(char c) {return CLOSERS.indexOf(c) >= 0;}
	private static boolean matches(char opener, char closer) {return OPENERS.indexOf(opener) == CLOSERS.indexOf(closer);}

	private static String 
		OPENERS = "([{<",
		CLOSERS = ")]}>";
}

The Driver

The Exception Class

public class DelimiterCheckerException extends Exception {
	public DelimiterCheckerException(String message) {
		super(message);
	}
}

Expression Evaluation

Infix, Prefix, Postfix Notation

1. Infix: a + b * c
   • Infix: a + (b * c) (parenthesized)
   • Postfix: a b c * +
   • Prefix: + a * b c
2. Infix: (a + b) * c
   • Postfix: a b + c *
   • Prefix: * + a b c

Postfix Expression Evaluation

	eval(expression)
		for each token t
			if t is an operand 
				push it on the stack
			else // t is an operator
				pop the right operand off the stack	
				pop the left operand off the stack	
				evaluate the simple expression a consisting of the operands and the operator,
					and push the result on the stack

		return the value on the stack

• A token is a unit of data in an input stream; in our case it's either an operand (sequence of digits) or a single character operator.
• The above algorithm assumes no errors (or other nasty details such as converting string input to numeric operands)
  • This is all taken care of in the actual code

A Java Implementation

import java.util.Scanner;
import java.util.Stack;

public class PostfixEval {
	public PostfixEval(String exp) {this.exp = exp;}

	public int eval() throws PostfixEvalException {
		Stack<Integer> evalStack = new Stack<>();;

		 Scanner scanner = new Scanner(exp);

		 while (scanner.hasNext()) {
			String token = scanner.next();
			if (isOperand(token))
				evalStack.push(Integer.parseInt(token));
			else if (isOperator(token)) {  
				if (evalStack.empty()) throw new PostfixEvalException("Missing operand");
				int operand2 = evalStack.pop();
				if (evalStack.empty()) throw new PostfixEvalException("Missing operand");
				int operand1 = evalStack.pop();
				evalStack.push(eval(token, operand1, operand2));
			}
			else
				throw new PostfixEvalException("unexpected token");
		}

		if (evalStack.empty()) throw new PostfixEvalException("Empty expression");
		int result = evalStack.pop();
		if (!evalStack.empty()) throw new PostfixEvalException("Missing operator(s)");
		return result;
	}

	// evaluate single operator expression
	private static int eval(String optr, int operand1, int operand2) throws PostfixEvalException {
		switch (optr) {
			case "+": return operand1 + operand2;
			case "-": return operand1 - operand2;
			case "*": return operand1 * operand2;
			case "/": 
				if (operand2 == 0) throw new PostfixEvalException("Division by 0");
				return operand1 / operand2;
		}
		throw new PostfixEvalException("Insanity check in eval");
	}

	String exp;

	static boolean isOperand(String token) {return Character.isDigit(token.charAt(0));} 
	static boolean isOperator(String token) {return OPERATOR_STRING.indexOf(token.charAt(0)) != -1;}

	final static String OPERATOR_STRING = "+-*/";
}

The Driver

public class PostfixEvalApp {
	public static void main(String [] args) {
		if (args.length == 1)
			doIt(args[0]);
		else
			for (String exp : exps)
				doIt(exp);
	}

	static private void doIt(String exp) {
		try {
			System.out.println(exp + " -> " + new PostfixEval(exp).eval());
		} catch (PostfixEvalException e) {
			System.out.println("*** " + e + ": " + exp);
		}
	}

	static String [] 
		exps = {
			"2 4 +",
			"6 1 -",
			"8 5 *",
			"12 4 /",
			"2 3 4 * +", 
			"2 3 + 4 *",
			"5",
			"2 3",
			"2 +",
			"+",
			""
		};
}

weiss$ java PostfixEvalApp
2 4 + -> 6
6 1 - -> 5
8 5 * -> 40
12 4 / -> 3
2 3 4 * + -> 14
2 3 + 4 * -> 20
5 -> 5
*** PostfixEvalException: Missing operator(s): 2 3
*** PostfixEvalException: Missing operand: 2 +
*** PostfixEvalException: Missing operand: +
*** PostfixEvalException: Empty expression: 

Infix To Postfix Conversion

1. 3 * 4 → 3 4 *
2. 3 * 4 + 5 → 3 4 * 5 +
3. 3 + 4 * 5 → 3 4 5 * +
4. 3 * (4 + 5) → 3 4 5 + *
5. 3 + 4 - 5 → 3 4 + 5 -

An Algorithm

infix-to-postfix(infixExp)
	result = ""
	while there is another token t
		if  t is an operand 
			append it to result
		else if t is a (
			push t on the stack
		else if t is a )
			while the top of the stack is not a (
				append the top of the stack to result and pop the stack
		else 	// t is an operator
			while the stack is NOT empty and the operator on top of the stack has higher precedence than t
				append the operator on top of the stack to result and pop the stack
			push t

	pop remaining elements from stack and append them to result
	return result

import java.util.Scanner;
import java.util.Stack;

public class InfixToPostfix {
public InfixToPostfix(String exp) {this.exp = exp;}

	public String convert() throws PostfixEvalException {
		Stack<String> opStack = new Stack<>();;
		String postfix = "";

		Scanner scanner = new Scanner(exp);

		while (scanner.hasNext()) {
			String token = scanner.next();

			if (isOperand(token))
				postfix += token + " ";
			else if (token.equals("(")) 		// '(' always gets pushed
				opStack.push(token);
			else if (isOperator(token)) {
				String optr = token;
				// Output any higher-prec operator on stack
				while (!opStack.empty() && !opStack.peek().equals("(") && precLevel(opStack.peek()) >= precLevel(optr)) {
					postfix += opStack.pop();
					postfix += " ";
				}
				opStack.push(optr);		// push current operator
			}
			else if (token.equals(")")) {	
				// Output all operators on stack until '('
				while (!opStack.empty() && !opStack.peek().equals("(")) {
					postfix += opStack.pop();
					postfix += " ";
				}
				if (opStack.empty()) throw new PostfixEvalException("Unmatched )");
				opStack.pop();
			}
			else
				throw new PostfixEvalException("Unexpected character");
		}

		// Output any remaining operators
		while (!opStack.empty()) {
			postfix += opStack.pop();
			postfix += " ";
		}

		return postfix;
	}

	private static int precLevel(String optr) throws PostfixEvalException {
		switch (optr) {
			case "+":
			case "-":
			return 1;

			case "*":
			case "/":
			return 2;
		}
		throw new PostfixEvalException("Insanity check in precLevel");
	}		

	String exp;

	static boolean isOperand(String token) {return Character.isDigit(token.charAt(0));} 
	static boolean isOperator(String token) {return OPERATOR_STRING.indexOf(token.charAt(0)) != -1;}

	final static String OPERATOR_STRING = "+-*/";
}