Program1.java

package justinhead.se3345;

import java.util.Arrays;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * Program 1
 * @author Justin Head
 */
public class Program1 {

    public static void main(String[] args) {
        String raw = "";
        
        /* Infix to postfix conversion */
        raw = "65 + 52 * 23 + ( 3 * 8 + 3 ) * 5";
        PostfixExpression exp = PostfixExpression.fromInfix("65 + 52 * 23 + ( 3 * 8 + 3 ) * 5");
        
        System.out.println("-=-= Infix to postfix conversion =-=-\nInput: " + raw + "\nOutput: " + exp + "\n");
        
        /* Postfix evaluation */
        raw = "6 5 2 3 + 8 * + 3 + *";
        double value = new PostfixExpression(raw).evaluate();
        
        System.out.println("-=-= Postfix evaluation =-=-\nInput: " + raw + "\nOutput: " + value + "\n");
    }
    
}

class PostfixExpression {
    
    public static final Map<Character, Integer> OPERATORS = new HashMap<>();
    
    static {
        OPERATORS.put('+', 0);
        OPERATORS.put('-', 0);
        OPERATORS.put('*', 1);
        OPERATORS.put('/', 1);
        OPERATORS.put('(', 2);
        OPERATORS.put(')', 2);
    }
    
    protected String expression = "";
    
    public PostfixExpression(String expression) {
        this.expression = expression;
    }
    
    @Override
    public String toString() {
        return expression;
    }
    
    public double evaluate() {
        Stack<Double> stack = new Stack<>();
        List<String> parts = PostfixExpression.tokenize(this.expression);
        
        for (String part : parts) {
            System.out.println(part + "\t" + stack.toString());
            
            Character singleChar = part.charAt(0);
            boolean isOperator = OPERATORS.containsKey(singleChar);
            
            if (isOperator) {
                if (stack.size() < 2) continue;
                
                double stackOne = stack.pop(),
                        stackTwo = stack.pop(),
                        result = 0d;
                
                switch (part) {
                    case "+":
                        result = stackTwo + stackOne;
                        break;
                    case "-":
                        result = stackTwo - stackOne;
                        break;
                    case "*":
                        result = stackTwo * stackOne;
                        break;
                    case "/":
                        result = stackTwo / stackOne;
                        break;
                }
                
                stack.push(result);
            } else {
                stack.push(Double.parseDouble(part));
            }
        }
        
        return stack.pop();
    }
    
    public static PostfixExpression fromInfix(String expression) {
        expression = expression.replaceAll(" ", "");
        
        Stack<Character> stack = new Stack<>();
        List<String> result = new LinkedList<>();
        List<String> parts = PostfixExpression.tokenize(expression);
        
        for (String part : parts) {
            Character singleChar = part.charAt(0);
            Character topOfStack = (stack.size() > 0 ? stack.peek() : null);
            boolean isOperator = OPERATORS.containsKey(singleChar);

            if (isOperator) {
                if (topOfStack == null) 
                    stack.push(singleChar);
                else {
                    int opPrec = OPERATORS.get(singleChar);
                    int tosPrec = OPERATORS.get(topOfStack);
                    
                    if (opPrec > tosPrec) {
                        if (singleChar != ')')
                            stack.push(singleChar);
                        else
                            while ((topOfStack = stack.pop()) != '(')
                                result.add(topOfStack.toString());
                    } else {
                        do {
                            if (topOfStack == '(' && singleChar != ')')
                                break;
                            
                            result.add((stack.pop() + "").replaceAll("/[\\(\\)]/g", ""));
                            topOfStack = (stack.size() > 0 ? stack.peek() : null);
                        } while (opPrec <= tosPrec && topOfStack != null);

                        stack.push(singleChar);
                    }
                }
            } else
                result.add(part);
        }

        if (stack.size() > 0) {
            Enumeration e = stack.elements();
            
            while (e.hasMoreElements())
                result.add(e.nextElement().toString());
        }
        
        String finalResult = "";
        
        for (String s : result)
            finalResult += s + " ";
        
        finalResult = finalResult.substring(0, finalResult.length() - 1);
        
        return new PostfixExpression(finalResult);
    }
    
    public static List<String> tokenize(String expression) {
        List<String> parts = new LinkedList<>();
        String[] rawParts = expression.split("(?=[^\\d])");
        
        for (String part : rawParts) {
            Character first = part.charAt(0);
            String numeric = part.replaceAll("[^\\d]", "");
            
            if (OPERATORS.containsKey(first))
                parts.add(first.toString());
            
            if (numeric.length() > 0)
                parts.add(numeric);
        }
        
        return parts;
    }
    
}