Using the Shunting Yard Algorithm to Write Truth Tables

If you’ve gone through the first year of a undergraduate Computer Science degree, you’ll have written enough truth tables to last you a lifetime. Personally, I decided I’d had enough halfway through the semester and wrote a program to write my truth tables for me in Go. Unfortunately, we’d moved on from the topic before I finished working on this, but I still think it’s a pretty interesting project.

The first step is to parse the formula and convert it into a form that can easily be evaluated. Normally, logical formulae are written like this: P ^ Q, P v (Q ^ R), or P ^ ~Q => R. The important thing to note is that binary operators like v and ^ are placed between their operands (i.e. the propositions). This is known as infix notation. Unfortunately, it’s harder to directly evaluate infix expressions because we have to take order of operations into account. For example, in P v (Q ^ R), Q ^ R has to be evaluated first. It would be much easier if we could evaluate an expression directly from left to right, in order.

Thankfully, there is a solution. In postfix, or Reverse Polish Notation, where operators are placed after the operands, the examples above would be written P Q ^, P Q R ^ v, and P Q ~ ^ R =>. If you don’t understand how these expressions came to be, don’t worry: we’re going to get to the conversion part in just a bit. However, a quick look at these postfix expressions will reveal the most important feature of RPN: operators are listed from left to right in the same order as they are to be applied. In P Q R ^ v, ^ is listed before v because Q ^ R is evaluated first. This removes the need for parentheses and PEMDAS, becuse we can evaluate the expression from left to right.

Being used to infix notation, it’s not immediately obvious which operands an operator applies to; however, it’s not difficult to understand, it’s just different. Each binary operator applies to the two operands directly to its left. Each unary operator similarly applies to the single operand directly to its left. When an operator doesn’t have an operand directly to its left but an expression instead, it applies to the result of that expression.

All right, enough about how great RPN is. How do we actually get there?

Dijkstra’s Shunting Yard Algorithm

(Yes, this is the Dijkstra of pathfinding fame.)

The basic operation of the shunting yard algorithm is as follows. The input expression is read character by character. Operands are sent directly to the ouput expression. Operators are sent to a stack. Because operators of higher precedence must be performed first, they must be popped off the stack and sent to the output expression before any operators of lower precedence are pushed onto the stack.

I’m not going to explain the algorithm in any more detail here because it would be redundant. Instead, I suggest you look at these wonderful notes.

The algorithm is named so because it can be visualised like a three-way/wye junction used in railway shunting yards. You can see a great diagram as well as a walkthrough of how it works here.

Both of these resources only deal with using the SYA for arithmetic expressions. However, adapting it for logical formulae is very easy. The main factor influencing the behavior of the algorithm is the precedence order of the operators, because that is what determines when an operator is popped off the stack and sent to the output. The precedence rules for the logical operators is: negation (NOT, conjunction (AND), disjunction (OR), implication (IF/THEN), and finally the biconditional (IFF). We can represent this by using a map, and assigning each operator a number indicating its precedence.

package main

import (
	"fmt"
	"strconv"
	"math"
)

var ops = make(map[byte]int)

func main() {
	ops['~'] = 5
	ops['^'] = 4
	ops['v'] = 3
	ops['>'] = 2
	ops['='] = 1
}

I’ve used some unconventional symbols for implication and biconditional, but using single characters makes parsing sooo much easier.

Before writing the shunting yard function, we need a small helper function to tell us whether a character is an operator or not:

func isOperator(tok byte) bool {
	_, exists = ops[tok]
	return exists
}

And now the star of the show, which is surprisingly straightforward.

func shuntingYard(exp string) []byte {
    out := []byte {}
    opStack := []byte {}

	// read each character one at a time
    for i := 0; i < len(exp); i++ {
        if isOperator(exp[i]) {
		    // pop all operators of higher precedence from the stack
            for {
                stackLength := len(opStack)

                if stackLength == 0 {
                    break
                }

                topOfStack := opStack[stackLength - 1]

				// stop when a ( is reached too
                if topOfStack == '(' || ops[topOfStack] < ops[exp[i]] {
                    break
                } else {
                    out = append(out, topOfStack)
                    opStack = opStack[:stackLength - 1]
                }
            } 

			// push the operator to the stack
            opStack = append(opStack, exp[i])
        } else if exp[i] == '(' {
	        // ( are pushed directly to the stack
            opStack = append(opStack, exp[i])
        } else if exp[i] == ')' {
	        // 'unwind' the stack by popping all operators
	        // between the () pair, checking to make sure that
	        // each ) has a matching (
            for {
                stackLength := len(opStack)

                if stackLength == 0 {
                    panic("Left and right parens do not match")
                }

                topOfStack := opStack[stackLength - 1]
                opStack = opStack[:stackLength - 1]

                if topOfStack == '(' {
                    break
                } else {
                    out = append(out, topOfStack)
                }
            }
        } else {
	        // operands are sent directly to the output
            out = append(out, exp[i])
        }
    }

	// Check if there are any ( without matching )
    for i := len(opStack); i > 0; i-- {
        if opStack[i - 1] == '(' {
            panic("Left and right parens do not match")
        }

        out = append(out, opStack[i - 1])
    }

    return out
}

There’s a fair bit more validation and error checking that could be done, but this is good enough.

To test this out, add this to main():

exp := "~p^(qv~r)"
fmt.Println(shuntingYard(exp))

go run . should produce the following line of output: p~qr~v^.

Evaluating RPN expressions

Great, now we have the formula all tidied up and in RPN. The next part is evaluating an RPN expression given truth values for each of the propositions involved. Interestingly, this also involves a stack.

The RPN expression is read from left to right, character by character. When we encounter an operand/proposition, its truth value is pushed directly onto the evaluation stack. Then, when we get to an operator, we need to apply it to the operands directly to its left. These are the values on the top of the evaluation stack, so we pop them off, perform the operation, then push the result back onto the stack for further use.

In code, this is pretty simply, if repetitive. We can simply use the built in logical operators that come with basically any programming language.

func evaluate(rpn []byte, values map[byte]bool) bool{
    evalStack := []bool {}

    for i := 0; i < len(rpn); i++ {
        if !isOperator(rpn[i]) {
            evalStack = append(evalStack, values[rpn[i]]) 
        } else {
            stackLen := len(evalStack)

            switch rpn[i] {
                case '~':
                    evalStack[stackLen - 1] = !evalStack[stackLen - 1]

                case '^':
                    evalStack[stackLen - 2] = evalStack[stackLen - 2] && evalStack[stackLen - 1]
                    evalStack = evalStack[:stackLen - 1]

                case 'v':
                    evalStack[stackLen - 2] = evalStack[stackLen - 2] || evalStack[stackLen - 1]
                    evalStack = evalStack[:stackLen - 1]

                case '>':
                    evalStack[stackLen - 2] = !evalStack[stackLen - 2] || evalStack[stackLen - 1]
                    evalStack = evalStack[:stackLen - 1]

                case '=':
                    evalStack[stackLen - 2] = evalStack[stackLen - 2] == evalStack[stackLen - 1]
                    evalStack = evalStack[:stackLen - 1]
            }
        }
    }

    return evalStack[0]
}

Strictly speaking, I didn’t implement a proper stack per se, but this is an entirely accurate and sufficient simulation of the behavior we need.

One thing I haven’t mentioned yet is the values map in the function above. It assigns a truth value to each proposition, but how do we generate this map for an arbitrary number of propositions?

Generating truth values

The systematic way of writing down truth values for atomic propositions in truth tables is equivalent to counting upwards in binary from 0 to 2^n, where n is the number of atomic propositions involved in the expression. For example,

is the same as

We can exploit this fact to generate our truth values for us. But first, we need to find all the unique identifiers for propositions in our epxression so we know how many there are.

func uniqueIdentifiers(exp string) ([]byte, int) {
    count := 0
    ids := []byte {}

    for i := 0; i < len(exp); i++ {
        tok := exp[i]
        exists := false

		// ignore operators
        if  isOperator(tok) || tok == '(' || tok == ')' {
            continue
        }

		// search through the slice of ids to check if we've
		// already encountered the current proposition
        for j := 0; j < count; j++ {
            if ids[j] == tok {
                exists = true
                break
            }
        }

		// make a note of any new propoitions
        if !exists {
            ids = append(ids, tok)
            count++
        }
    }

    return ids, count
}

With ids, the slice of identifiers this function returns, we can now generate a set of truth values given which row of the truth table we’re on.

func generateValues(ids []byte, row int) map[byte]bool {
    bin := strconv.FormatInt(int64(row), 2)
    for len(bin) < len(ids) {
        bin = "0" + bin
    }

    vals := make(map[byte]bool)

    for i := 0; i < len(ids); i++ {
        if bin[i] == '0' {
            vals[ids[i]] = false
        } else {
            vals[ids[i]] = true
        }
    }

    return vals
}

The strconv package can conveniently turn a number into a binary representation for us, but we need to pad it to the right length (i.e. the number of propositions in ids) ourselves. Then, it’s a simple matter of assigning each identifier true or false based on the corresponding character in the binary string.

Tying it all together

With everything in place, all that’s left to do is some bits of code to get an expression as input from the user and to print the truth table out to the terminal.

    // func main() {
    var exp string
    fmt.Print("Enter an expression: ")
    fmt.Scan(&exp)

    rpn := shuntingYard(exp)
    ids, count := uniqueIdentifiers(exp)

    fmt.Println()
    for i := 0; i < count; i++ {
        fmt.Printf("%c\t", ids[i])
    }
    fmt.Println(exp)

    for i := 0; i < int(math.Pow(float64(2), float64(count))); i++ {
        truthValues := generateValues(ids, i)
        
        for j := 0; j < count; j++ {
            fmt.Printf("%v\t", truthValues[ids[j]])
        }

        result := evaluate(rpn, truthValues)
        fmt.Println(result)
    }

You can find the entire, finished program here.

Wrapping it up

While not particularly difficult, I think this project was overall quite interesting, both in terms of the algorithms I learned about and my own approaches to implementing them. There’s plenty of scope to add more features, such as printing each subexpression out in its own column to make an expanded version of the truth table. Honestly though, this blog post is long enough already.

Also, I first built this tool in Python. Only much later did I start learning Go and decide that this would be a good starting point towards building more complicated pieces of software. So far, I really like Go, but this isn’t the place to talk about that in detail - maybe in a future post.

For now, I need to do something that doesn’t involve truth tables. I’ve seen more than enough to last me a lifetime.