Adding unary operator to shunting yard algorithm

Question

I am creating a calculator-type program that parses an input into postfix notation and then evaluates the expression. It works for +,-,*,/, and ^, but I cannot get the unary - to work. Currently I am just trying to get the unary - to work at the start of an expression. I am using -5+2 to test the algorithm. The return result should be -3, however, I the program is returning -2. I have marked the 2 places in my code that I am trying to handle the unary - sign as

//-------------HERE IS WHERE I TRY TO HANDLE UNARY - as "u"----------------------------

I have been debugging all day and cannot figure out what is not working. Here is my code:

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

public class Calculator {

    public static void main(String[] args) {
        ArrayList test = new ArrayList();
        Scanner f = new Scanner(System.in);

        System.out.println("Type and equation, then press enter: ");

        String g = f.nextLine();

        test = inputToArrayList(g);

        for (int z = 0; z < test.size(); z++) {
            System.out.println(test.get(z));
        }

        System.out.println(calculateAnswer(test));
    }

    public static class SyntaxErrorException extends Exception {

        SyntaxErrorException(String message) {
            super(message);
        }
    }
    private static final Stack<Double> operandStack = new Stack<Double>();
    private static final Stack<String> operatorStack = new Stack<String>();
    private static final String OPERATORS = "+-/*%^()u";
    private static final String NONBRACES = "+-/*%^u";
    private static final int[] PRECEDENCE = {1, 1, 2, 2, 2, 3, 3, 3, 4};

    static ArrayList<String> charList = new ArrayList<String>();

    public static ArrayList inputToArrayList(String input) {
        StringBuilder strBuild = new StringBuilder();
        String infix = input.replace(" ", "");
        try {
            for (int i = 0; i < infix.length(); i++) {
                char c = infix.charAt(i);

                boolean isNumber = (c >= '0' && c <= '9');
//------------HERE IS WHERE I HANDLE - AT BEGINNING OF INPUT, SAVED AS U INSTEAD OF -   ----------
                if (i == 0 && c == '-') {
                    isNumber = true;
                    charList.add("u");
                    continue;
                }

                if (isNumber) {
                    strBuild.append(c);
                    if (i == infix.length() - 1) {
                        charList.add(strBuild.toString());
                        strBuild.delete(0, strBuild.length());
                    }
                } else if (c == '.') {
                    for (int j = 0; j < strBuild.length(); j++) {
                        if (strBuild.charAt(j) == '.') {
                            throw new SyntaxErrorException("You can't have two decimals in a number");
                        } else if (j == strBuild.length() - 1) {
                            strBuild.append(c);
                            j = (strBuild.length() + 1);
                        }
                    }
                    if (strBuild.length() == 0) {
                        strBuild.append(c);
                    }
                    if (i == infix.length() - 1) {
                        throw new SyntaxErrorException("You can't end your equation with a decimal");
                    }
                } else if (OPERATORS.indexOf(c) != -1) {
                    if (strBuild.length() != 0) {
                        charList.add(strBuild.toString());
                        strBuild.delete(0, strBuild.length());
                    }
                    strBuild.append(c);
                    charList.add(strBuild.toString());
                    strBuild.delete(0, strBuild.length());
                } else {
                    throw new SyntaxErrorException("Make sure your input only contains numbers, operators, or parantheses");
                }
            }

            int leftParenth = 0;
            int rightParenth = 0;

            for (int p = 0; p < charList.size(); p++) {
                String checkParenth = charList.get(p);

                switch (checkParenth) {
                    case "(":
                        leftParenth++;
                        break;
                    case ")":
                        rightParenth++;
                        break;
                    default: //do nothing
                        break;
                }

            }
            if (leftParenth != rightParenth) {
                throw new SyntaxErrorException("There is not an even number of parenthesis");
            }

            int parenthesis = 0;

            for (int f = 0; f < charList.size(); f++) {
                String awesome = charList.get(f);
                switch (awesome) {
                    case "(":
                        parenthesis++;
                        break;
                    case ")":
                        parenthesis--;
                        break;
                    default:
                        break;
                }
                if (parenthesis < 0) {
                    throw new SyntaxErrorException("Order of parenthesis is off");
                }
            }
            if (NONBRACES.contains(charList.get(charList.size() - 1))) {
                throw new SyntaxErrorException("The input can't end in an operator");
            }
            return charList;
        } catch (SyntaxErrorException ex) {
            System.out.println(ex);
            return charList;
        }
    }

    private static void processOperator(String op) {
        if (operatorStack.empty() || op.equals("(")) {
            operatorStack.push(op);
        } else {
            //peek the operator stack and
            //let topOp be the top operator.
            String topOp = operatorStack.peek();
            if (precedence(op) > precedence(topOp)) {
                if (!op.equals(")")) {
                    operatorStack.push(op);
                }
            } else {
                //Pop all stacked operators with equal
                // or higher precedence than op.
                while (!operatorStack.empty() && precedence(op) >= precedence(topOp)) {
 //-------------HERE IS WHERE I TRY TO HANDLE UNARY - and "u"----------------------------                   
                    if("u".equals(operatorStack.peek())) {
                        double right = operandStack.pop();
                        String unary = operatorStack.pop();
                        operandStack.push(right * (-1));
                        break;
                    }
                    double right = operandStack.pop();
                    double left = operandStack.pop();
                    String operator = operatorStack.pop();
                    switch (operator) {
                        case "+":
                            operandStack.push(left + right);
                            break;
                        case "-":
                            operandStack.push(left - right);
                            break;
                        case "*":
                            operandStack.push(left * right);
                            break;
                        case "/":
                            operandStack.push(left / right);
                            break;
                        case "%":
                            operandStack.push(left % right);
                            break;
                        case "^":
                            operandStack.push(Math.pow(left, right));
                            break;
                        default: //do nothing, but this should never happen
                            break;
                    }

                    if (topOp.equals("(")) {
                        //matching '(' popped - exit loop.
                        operandStack.push(left);
                        operandStack.push(right);
                        break;
                    }

                    if (!operatorStack.empty()) {
                        //reset topOp
                        topOp = operatorStack.peek();
                    }
                }

                //assert: Operator stack is empty or
                // current operator precedence > top of stack operator precedence.
            }
        }
    }

    public static String calculateAnswer(ArrayList<String> infix) {
        int p;
        for (p = 0; p < infix.size(); p++) {
            if (!OPERATORS.contains(infix.get(p))) {
                double listIndex = Double.parseDouble(infix.get(p));
                operandStack.push(listIndex);
            } else {
                processOperator(infix.get(p));
            }
        }
        if (p == infix.size()) {
            while (!operatorStack.empty()) {
                if ("u".equals(operatorStack.peek())) {

                    double right = operandStack.pop();
                    String unary = operatorStack.pop();
                    operandStack.push(right * (-1));
                    break;
                }
                double right = operandStack.pop();
                double left = operandStack.pop();
                String current = operatorStack.pop();
                switch (current) {
                    case "+":
                        operandStack.push(left + right);
                        break;
                    case "-":
                        operandStack.push(left - right);
                        break;
                    case "*":
                        operandStack.push(left * right);
                        break;
                    case "/":
                        operandStack.push(left / right);
                        break;
                    case "%":
                        operandStack.push(left % right);
                        break;
                    case "^":
                        operandStack.push(Math.pow(left, right));
                        break;
                    default: //do nothing, but this should never happen
                        break;
                }
            }
        }
        return String.valueOf(operandStack.pop());
    }

    private static int precedence(String op) {
        return PRECEDENCE[OPERATORS.indexOf(op)];
    }
}

Answer 1

This is not a trivial problem to solve. Dijkstra's original algorithm was explicitly for infix operators and mentions (but doesn't solve) prefix or postfix operators. So there is no simple extension that universally handles unary operators.

You will need to store additional state; specifically, the last type of element parsed and whether you are in a 'inverse' state. If it's an operator or nothing (i.e. start of expression) then '-' should toggle the 'inverse' state. Numbers should check and clear the inverse state and *= -1 if necessary before adding to stack. In other words, this becomes a way of handling the unary operator as a part of the constant rather than as an operator.

Note those two paragraphs aren't contradictory! The solution above won't handle 3 * -(5 + 2) because it's not treating the '-' as an operator but, rather, a flag used when numbers are read.

Also note that the 'proper' solution here is to not use the shunting yard algorithm when your operators aren't all infix. Use a proper grammar parser (e.g. Yacc).

Answer 2

If we look at the precedence tables of programming languages see Order of Operations (Wikipedia) we see that the unary operators have a different precedence level to the corresponding infix operator. The table generally looks like

1. () brackets
2. +-! unary operators
3. */ multiply and divide
4. +- infix addition and subtraction
5. == comparision operators
6. = assignment operators

so your program needs a way of distinguishing between unary and binary operators with the same symbol. In Dijkstra work he gives unary minus the same precedence as * and /, but does not address how the parser distinguishes unary and binary cases.

I've successfully followed the technique in Parsing Expressions by Recursive Descent this is very similar to the shunting yard algorithm, but with a bit of recursion to handle the brackets.

We can divide our syntax into two parts: prefix-suffix expressions, P, which includes numbers, identified, unary operators (both as prefix and as suffixes), and bracketed expressions. Full expressions, E, are a bunch of P's separated by binary operators.

P :: number
   | identifier i.e. varible name
   | -P  prefix operator followed by a P
   | ( E ) an E in brackets

The expression E will be

E :: P
  | P + E | P - E | P * E | P / E

i.e. a sequence of P's with binary operators between them say P+P+P-P.

For the E part you use a shunting yard but for P there is a bit of recursion. His algorithm is

Eparser is
   var operators : Stack of Operator := empty
   var operands : Stack of Tree := empty
   push( operators, sentinel )
   E( operators, operands )
   expect( end )
   return top( operands )

E( operators, operands ) is
    P( operators, operands )
    while next is a binary operator
       pushOperator( binary(next), operators, operands )
       consume
       P( operators, operands )
    while top(operators) not= sentinel
       popOperator( operators, operands )

P( operators, operands ) is
    if next is a v
         push( operands, mkLeaf( v ) )
         consume
    else if next = "("
         consume
         push( operators, sentinel )   -- pushes sentinel
         E( operators, operands )      -- note recursion
         expect( ")" )                 -- remove bracket from input
         pop( operators )              -- pops sentinel
    else if next is a unary operator
         pushOperator( unary(next), operators, operands )
         consume
         P( operators, operands )
    else
         error

popOperator( operators, operands ) is
   if top(operators) is binary
        const t1 := pop( operands )
        const t0 := pop( operands )
        push( operands, mkNode( pop(operators), t0, t1 ) )
   else
        push( operands, mkNode( pop(operators), pop(operands) ) )

pushOperator( op, operators, operands ) is
    while top(operators) > op
       popOperator( operators, operands )
    push( op, operators )

Note there is a recursive step when an open brackets is encountered. First sentinel is pushed onto the operator stack, this is some special operator used to prevent too many operators being poped. The code then calls E again. E will run until the closing brace is discovered. When E ends all the operators up to the first sentinel are popped from the stack.