javastackevaluator

Evaluator Expression: How to know if the input is wrong


I'm solving the next technical question (Q1): http://blog.sdeskills.com/qotd-2016-oct-17-resistance-is-futile/

It's almost done, just one task is pending. Evaluate if the input is balanced or not. Checking if parenthesis are in order, that's done, but not to evaluate the tokens.

In a given sub-network cannot have a mix of series / parallel connections, so (500+200|300) is not allowed.

This is my current code: https://repl.it/EC3i/2 Any idea about how to evaluate the previous expression as wrong?


Solution

  • Try this. This code checks operator sereis and also balanced parentheses.

    static boolean isBalanced(String s) {
        Deque<Character> operators = new LinkedList<>();
        operators.push('#');
        for (int i = 0; i < s.length(); ++i) {
            if (operators.isEmpty()) return false;
            char ch = s.charAt(i);
            switch (ch) {
            case '(': operators.push('#'); break;
            case ')': operators.pop(); break;
            case '+':
                switch (operators.peek()) {
                case '#': operators.pop(); operators.push(ch); break;
                case '+': break;
                default: return false;
                }
                break;
            case '|':
                switch (operators.peek()) {
                case '#': operators.pop(); operators.push(ch); break;
                case '|': break;
                default: return false;
                }
                break;
            }
        }
        return operators.size() == 1;
    }
    

    And JUnit test codes.

    @Test
    public void testIsBalanced() {
        assertTrue(isBalanced("(2)"));
        assertTrue(isBalanced("(2+3+3)"));
        assertTrue(isBalanced("2+3+3"));
        assertTrue(isBalanced("2+(4|5|5)+3"));
        assertTrue(isBalanced("2+(4|(2+3+4)|5)+3"));
        assertTrue(isBalanced("(2)+3()"));
        assertFalse(isBalanced("(2"));
        assertFalse(isBalanced("(2))"));
        assertFalse(isBalanced("((2)"));
        assertFalse(isBalanced("2|3+3"));
        assertFalse(isBalanced("2+(4|5+5)+3"));
        assertFalse(isBalanced("2+3|3"));
    }