Expression evaluation using two stacks

Question

I tried to evaluate an expression using two stacks (operands stack and operators stack). For now I just want to test my program with addition and subtraction but it keeps return 0, I guess it didn't do math right. Please help

public static void main(String[] args) {

    int userChoice;
    String expression;
    int finalresult;

    Scanner keyboard = new Scanner(System.in);
    System.out.println("  1. Keyboard");
    System.out.println("  2. From a file");
    System.out.println();
    System.out.print("Select (1), (2): ");

    // Integer Stack that is used to store the integer operands
    GenericStack<Integer> stackForOperands = new GenericStack<Integer>();
    // Character Stack that is used to store the operators
    GenericStack<Character> stackForOperators = new GenericStack<Character>();

    userChoice = keyboard.nextInt();
    switch (userChoice) {
    case 1:
        System.out.print("Please enter an expression seperated by space: ");
        keyboard.nextLine();
        expression = keyboard.nextLine();
        String[] tokens = expression.split("\\s+");
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].matches("-?\\d+")) {
                stackForOperands.push(Integer.parseInt(tokens[i]));
            } else {
                if (tokens[i] == "+" || tokens[i] == "-") {// if the extracted item is a + or – operator                                                                                                                                                                                                                
                    if (stackForOperators.isEmpty())
                        stackForOperators.push(tokens[i].charAt(0));
                    else {
                        if (tokens[i] == "*" || tokens[i] == "/")
                            stackForOperators.push(tokens[i].charAt(0));
                        //else
                            // int top = stackForOperators.getTop();
                            // while (top != -1) {
                            //oneOperatorProcess(stackForOperands, stackForOperators);
                        // top = top - 1;
                        // }
                    }
                }// end of checking "+", "-"
            }
        }
        oneOperatorProcess(stackForOperands, stackForOperators);
        finalresult = stackForOperands.pop();
        System.out.println(finalresult);
    }
}

My method to perform operation

public static void oneOperatorProcess(GenericStack val, GenericStack op) {
    char operator = (char) op.getTop();
    int a = (int) val.pop();
    int b = (int) val.pop();
    int result = 0;
    switch (operator) {
    case '+':
        result = a + b;
        break;
    case '-':
        result = a - b;
        break;
    case '*':
        result = a * b;
        break;
    case '/':
        result = a / b;
        break;
    default:
        //return 0;
    }
    val.push((int) result);
    //return result;

Well GenericStack is basically a Stack that accept any data type. I used a simple expression like 5 + 3 but it won't work for anything similar — San Luong, Mar 05 '15 at 19:46
Don't write your own, Java has a stack http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html — weston, Mar 05 '15 at 19:47
Are you attempting to implement shunting yard: http://en.wikipedia.org/wiki/Shunting-yard_algorithm — weston, Mar 05 '15 at 19:47
Oh, I forgot to tell you that's the requirement of this assignment. I am not allowed to use the Stack of Java — San Luong, Mar 05 '15 at 19:56
Do **not** compare strings with `==` in Java. Use `equals(...)`. See: http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java — Bart Kiers, Mar 05 '15 at 19:58

score 1 · Answer 1 · edited May 23 '17 at 11:50

Run the app. Type some stuff in. Check the result. Repeat.

Is a very slow way to develop! It is also hard to do as the number of test cases gets larger and you won't know if you've broken a previously working case unless you manually try everything, every time.

Unit testing to the rescue

You need to look into unit testing, here I have used JUnit to add tests one at a time to slowly build up a full test harness that is painless to run. Read up on TDD for more info.

import static org.junit.Assert.*;    
import org.junit.Test;

public class ExpressionTests {

    @Test
    public void oneNumber() {
        assertEquals(123, new ExpressionEval().evaluate("123"));
    }

    @Test
    public void addTwoNumbers() {
        assertEquals(3, new ExpressionEval().evaluate("1 + 2"));
    }

    @Test
    public void subtractTwoNumbers() {
        assertEquals(2, new ExpressionEval().evaluate("5 - 3"));
    }

    @Test
    public void addThreeNumbers() {
        assertEquals(8, new ExpressionEval().evaluate("1 + 2 + 5"));
    }
}

The class starts to look like this below:

You had a number or errors like == for string comparison. See How do I compare strings in Java?

Also no while loop meant you would only manage one simple sum and couldn't handle no operator at all.

private class ExpressionEval {

    private final Stack<Integer> stackForOperands = new Stack<Integer>();
    private final Stack<Character> stackForOperators = new Stack<Character>();

    public int evaluate(String expression) {
        String[] tokens = expression.split("\\s+");
        for (String token : tokens) {
            if (token.matches("-?\\d+")) {
                stackForOperands.push(Integer.parseInt(token));
            } else {
                if ("+".equals(token) || "-".equals(token)) {
                    stackForOperators.push(token.charAt(0));
                }
            }
        }
        while (!stackForOperators.isEmpty())
            oneOperatorProcess();
        return stackForOperands.pop();
    }

    private void oneOperatorProcess() {
        char operator = stackForOperators.pop();
        int b = stackForOperands.pop();
        int a = stackForOperands.pop();
        int result = 0;
        switch (operator) {
        case '+':
            result = a + b;
            break;
        case '-':
            result = a - b;
            break;
            //Add others only when you have a test case that needs it.
        }
        stackForOperands.push(result);
    }

}

score 0 · Answer 2 · answered Mar 05 '15 at 19:56

Your logic is a little messed up. For example:

if (tokens[i] == "+" || tokens[i] == "-") {// if the extracted item is a + or – operator                                                                                                                                                                                                                
    if (stackForOperators.isEmpty())
        stackForOperators.push(tokens[i].charAt(0));
    else {
        //this will always eval to false because you can only get here if tokens[i] is + or -
        if (tokens[i] == "*" || tokens[i] == "/")
            stackForOperators.push(tokens[i].charAt(0));
    }
 }

Also, as @BartKiers mentioned in his comment, do tokens[i].equals(...) to compare your strings.

Expression evaluation using two stacks

2 Answers2

Unit testing to the rescue