CareerCup

Tried to solve it with a complex logic and it kind of worked but there were too many raise conditions and the code wasn't readable at all.
Using the Dijkstra 2 stack algorithm it is pretty elegant.

public class EvaluateMathematicalExpression {
    Map<Character, Integer> variables;

    public EvaluateMathematicalExpression(Map<Character, Integer> variables) {
        this.variables = variables;                
    }

    public static void main(String[] args){
        Map<Character, Integer> variables = new HashMap<>();
        List<String> expressions = new ArrayList<>();

        Scanner scan = new Scanner(System.in);

        System.out.println("enter number of variables:");
        int variablesNumber = scan.nextInt();
        scan.nextLine();

        System.out.println("now the variables: ");
        for(int i = 0; i<variablesNumber;i++){
            String line = scan.nextLine();
            String[] varVal = line.split("=");
            variables.put(varVal[0].charAt(0),Integer.valueOf(varVal[1]));
        }

        System.out.println("--------------");
        System.out.println("enter number of expressions:");
        int expressionsNumber = scan.nextInt();
        scan.nextLine();

        System.out.println("and the expressions: ");
        for(int i = 0; i<expressionsNumber;i++) {
            expressions.add(scan.nextLine());
        }


        EvaluateMathematicalExpression eme = new EvaluateMathematicalExpression(variables);

        for(String line : expressions){
            try{
                System.out.println("Evaluation of " + line + ": " + eme.evaluateDijkstra(line));
            } catch (Exception e){
                System.out.println("Compile error for " + line);
            }

        }

    }

    public int evaluateDijkstra(String expression){
        char[] chars = expression.toCharArray();

        Stack<Integer>    vals = new Stack<>();
        Stack<Character> ops  = new Stack<>();

        for(int i = 0; i<chars.length;i++){
            char currCh = chars[i];
            if(currCh == ' ') continue;

            if(isSign(currCh)){

                if(!ops.empty() && shouldCalcPrev(currCh, ops.peek())){
                    while(!ops.empty() && ops.peek() != null) {
                        char sign = ops.pop();
                        int right = vals.pop();
                        int left = vals.pop();
                        vals.push(calc(left, right, sign));
                    }
                    ops.push(currCh);
                } else {
                    ops.push(currCh);
                }
            } else {
                Integer val = variables.get(currCh);
                if(val == null){
                    throw new IllegalArgumentException("Unexpected character " + currCh);
                }
                vals.push(val);
            }
        }

        while(!ops.empty()){
            char sign = ops.pop();
            int right = vals.pop();
            int left  = vals.pop();
            vals.push(calc(left,right,sign));
        }

        return vals.pop();
    }

    public int calc(int left, int right, char ch){
        if(ch == '+'){
            return left + right;
        } else if(ch == '-'){
            return left - right;
        } else if(ch == '*'){
            return left * right;
        } else if(ch == '/'){
            return left / right;
        } else {
            throw new IllegalArgumentException("Compilation error, sign expected");
        }
    }

    /**
     * "*" and "/" get higher priority, if we reached to "+" and "-", we can(and should) calculate previous operations.
     * @param sign
     * @param prevSign
     * @return
     */
    public boolean shouldCalcPrev(char sign, Character prevSign){
        if(prevSign == null){
            return false;
        }
        if( (sign == '+' || sign == '-') && (prevSign == '*' || prevSign == '/')) return true;
        return false;
    }

    public boolean isSign(char ch){
        if(ch == '-' || ch == '+' || ch == '*' || ch == '/') return true;
        return false;
    }

}

Dijkstra's shunting yard algorithm is needed if we have to support parentheses. this problem is a special case: an expression only has binary operators and just 2 levels of precedence. this is a simpler solution to this problem:

public class EvaluateExpression {
    private static abstract class Node {
        Node left;
        Node right;
    }
    private static class Operator extends Node {
        char op;
        Operator (char op) {
            super();
            this.op = op;
        }
    }
    private static class Operand extends Node {
        int value;
        Operand(int value) {
            super();
            this.value = value;
        }
    }

    private final Map<Character, Integer> idToValue;

    //precedence: usual (* and / higher than + and -)
    //associativity: usual (left to right)
    // assume: operands are single letters
    // assume: integer arithmatic (no floating points)
    // assume: expression contains operands, operators and spaces only.
    public EvaluateExpression(List<String> assignments) {
        this.idToValue = new HashMap<>();
        for (String assignment: assignments) {
            assignment = assignment.replaceAll(" ", "");
            String[] parts = assignment.split("=");
            char id = parts[0].charAt(0);
            int value = Integer.parseInt(parts[1]);
            idToValue.put(id, value);
        }
    }

    private static int skipSpaces(String expression, int i) {
        for (; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c != ' ') {
                break;
            }
        }

        return i;
    }

    public int parseExpression(String expression) {
        //represent the expression as a list of operands and operators
        Node head = null;
        Node tail = null;
        boolean expectOperand = true;
        for (int i = skipSpaces(expression, 0); i < expression.length(); i++, i = skipSpaces(expression, i)) {
            char c = expression.charAt(i);
            if (expectOperand) {
                if (!idToValue.containsKey(c)) {
                    throw new IllegalArgumentException();
                }
                int value = idToValue.get(c);
                Node operand = new Operand(value);
                if (head == null) {
                    head = operand;
                    tail = operand;
                } else {
                    operand.left = tail;
                    tail.right = operand;
                    tail = operand;
                }
                expectOperand = false;
            } else {
                if ((c != '+') && (c != '-') && (c != '*') && (c != '/')) {
                    throw new IllegalArgumentException();
                }
                Node operator = new Operator(c);
                operator.left = tail;
                tail.right = operator;
                tail = operator;
                expectOperand = true;
            }
        }

        if (expectOperand) {
            throw new IllegalArgumentException("compilation error");
        }

        //evaluate all * and /
        Set<Character> operatorsToEvaluate = new HashSet<>();
        operatorsToEvaluate.add('/');
        operatorsToEvaluate.add('*');
        head = evaluateLeftToRight(head, operatorsToEvaluate);

        //evaluate all + and -
        operatorsToEvaluate.remove('/');
        operatorsToEvaluate.remove('*');
        operatorsToEvaluate.add('+');
        operatorsToEvaluate.add('-');
        head = evaluateLeftToRight(head, operatorsToEvaluate);

        return ((Operand)head).value;
    }

    private int evaluate(Operator operator) {
        int operand1 = ((Operand)operator.left).value;
        int operand2 = ((Operand)operator.right).value;
        char op = operator.op;
        int value;
        switch(op) {
            case '+': value = operand1 + operand2; break;
            case '-': value = operand1 - operand2; break;
            case '*': value = operand1 * operand2; break;
            case '/': value = operand1 / operand2; break;
            default:
                throw new IllegalArgumentException();
        }

        return value;
    }

    private Node evaluateLeftToRight(Node head, Set<Character> operatorsToEvaluate) {
        for (Node node = head; node != null; node = node.right) {
            if (!(node instanceof Operator)) {
                continue;
            }
            Operator operator = (Operator)node;
            if (!operatorsToEvaluate.contains(operator.op)) {
                continue;
            }
            int value = evaluate(operator);
            Operand operand = new Operand(value);
            operand.left = operator.left.left;
            operand.right = operator.right.right;
            if (operator.left.left != null) {
                operator.left.left.right = operand;
            } else {
                head = operand;
            }
            if (operator.right.right != null) {
                operator.right.right.left = operand;
            }
            node = operand;
        }

        return head;
    }

    private static void test(EvaluateExpression evaluator, String expression, int expected) {
        int actual = evaluator.parseExpression(expression);
        assert (actual == expected);
    }

    private static void negativeTest(EvaluateExpression evaluator, String expression) {
        try {
            evaluator.parseExpression(expression);
        } catch (IllegalArgumentException e) {
            return; //success
        }

        assert (false); //fail
    }

    private static void test() {
        List<String> assignments = Arrays.asList("a = 3", "b=8", " c =5", "d = 6 ");
        EvaluateExpression evaluator = new EvaluateExpression(assignments);

        test(evaluator, "a + b + c", 16);
        test(evaluator, "a + b - c", 6);
        test(evaluator, "b - a * c", -7);
        test(evaluator, "d / a + c - b", -1);
        test(evaluator, "a + b * c - d", 37);
        test(evaluator, "a*b*c - d", 114);
        test(evaluator, "b", 8);
        test(evaluator, "b + b", 16);
        test(evaluator, "b / b", 1);
        test(evaluator, "b / b / b", 0);
        test(evaluator, "b / a / b", 0);
        test(evaluator, "b / a + d", 8);
        test(evaluator, "c-a", 2);
        test(evaluator, "c-a ", 2);
        test(evaluator, "c- a ", 2);
        test(evaluator, "c -a ", 2);
        test(evaluator, " c-a", 2);
        test(evaluator, " c -   a", 2);

        negativeTest(evaluator, "");
        negativeTest(evaluator, " ");
        negativeTest(evaluator, " x ");
        negativeTest(evaluator, "a + * b");
        negativeTest(evaluator, "a + x");
        negativeTest(evaluator, "a + b * c /");
        negativeTest(evaluator, "-a + b * c");

        EvaluateExpression evaluator2 = new EvaluateExpression(Arrays.asList("a=1", "b=2", "c=2"));
        test(evaluator2, "a*b + a*c + b*c", 8);
        test(evaluator2, "a*c - b/c + c*c", 5);

        EvaluateExpression evaluator3 = new EvaluateExpression(Arrays.asList("g=2", "p=3", "t=1", "w=2"));
        test(evaluator3, "g + p*t - w*p", -1);
        test(evaluator3, "t - g + t - w", -2);
        negativeTest(evaluator3, "e + t*t -m");
    }

    public static void main(String[] args) {
        test();
    }

Functional-style Python 2.7 version. Parsing is bare-bone, it expects spaces and newlines as per the two examples above.

OPERATORS = ["+", "-", "x", "/"]
OPERATOR_TO_EVALUATOR = { 
  "+" : lambda x, y: x + y, 
  "-" : lambda x, y: x - y,
  "x" : lambda x, y: x * y,
  "/" : lambda x, y: x / y
}

def evaluate(prg):  
  blocks = prg.strip().split("\n\n")
  declarations, expressions = map(lambda b: b.split("\n"), blocks)
  env = make_env(declarations)
  for string in expressions:
    print evaluate_exp(string, env, 0)

def make_env(declarations):
  env = {}
  for line in declarations:
    variable, value = line.split(" = ")
    env[variable] = int(value)
  return env

def evaluate_exp(string, env, i):
  if i == len(OPERATORS):
    return env[string]
  else:
    operator = OPERATORS[i]
    sub_strings = string.split(" " + operator + " ")
    sub_exps = map(lambda s: evaluate_exp(s, env, i + 1), sub_strings)
    return reduce(OPERATOR_TO_EVALUATOR[operator], sub_exps)

Function style Python 2.7 version. Parsing is bare bone, newlines and spaces have to be put like in the above examples.

OPERATORS = ["+", "-", "x", "/"]
OPERATOR_TO_EVALUATOR = { 
  "+" : lambda x, y: x + y, 
  "-" : lambda x, y: x - y,
  "x" : lambda x, y: x * y,
  "/" : lambda x, y: x / y
}

def evaluate(prg):  
  blocks = prg.strip().split("\n\n")
  declarations, expressions = map(lambda b: b.split("\n"), blocks)
  env = make_env(declarations)
  for string in expressions:
    print evaluate_exp(string, env, 0)

def make_env(declarations):
  env = {}
  for line in declarations:
    variable, value = line.split(" = ")
    env[variable] = int(value)
  return env

def evaluate_exp(string, env, i):
  if i == len(OPERATORS):
    return env[string]
  else:
    operator = OPERATORS[i]
    sub_strings = string.split(" " + operator + " ")
    sub_exps = map(lambda s: evaluate_exp(s, env, i + 1), sub_strings)
    return reduce(OPERATOR_TO_EVALUATOR[operator], sub_exps)

Function style Python 2.7 version. Parsing is bare bone, newlines and spaces have to be put like in the above examples.

OPERATORS = ["+", "-", "x", "/"]
OPERATOR_TO_EVALUATOR = { 
  "+" : lambda x, y: x + y, 
  "-" : lambda x, y: x - y,
  "x" : lambda x, y: x * y,
  "/" : lambda x, y: x / y
}

def evaluate(prg):  
  blocks = prg.strip().split("\n\n")
  declarations, expressions = map(lambda b: b.split("\n"), blocks)
  env = make_env(declarations)
  for string in expressions:
    print evaluate_exp(string, env, 0)

def make_env(declarations):
  env = {}
  for line in declarations:
    variable, value = line.split(" = ")
    env[variable] = int(value)
  return env

def evaluate_exp(string, env, i):
  if i == len(OPERATORS):
    return env[string]
  else:
    operator = OPERATORS[i]
    sub_strings = string.split(" " + operator + " ")
    sub_exps = map(lambda s: evaluate_exp(s, env, i + 1), sub_strings)
    return reduce(OPERATOR_TO_EVALUATOR[operator], sub_exps)