Code n' Stuff

One of the very first exercises I did as a coding exercise was creating a simple (and crappy) calculator. It was very basic and did not need to consider order of operations. Below is a really basic example of what I mean:

But what if you wanted to calculate using more than one operation? Or be even more flexible and let a user pass in a string to calculate? In this situation, order of operations becomes something to take note of. When researching this, I stumbled upon polish notation (also called prefix notation) and the use of stacks as a solution to this problem.

Polish notation is a different way to write arithmatic. The operator is placed to the left of the operand. This was initially strange to me because I was used to infix notation. In infix, we place the operator in between the operands we are calculating. I did not realize there was any other way and infix was the most intuitive to me. It’s the more conventional way we read expressions.

An example of infix:
2 + 3

An example of prefix:
+ 2 3

While infix might be easier for me to read, I found that when trying to make a calculator, prefix was easier for a computer. One reason is that the rules of order of operations becomes unnecessary with prefix. When trying to calculate infix, there are a lot of rules to keep in mind.

For example:
(5 - 6) * 7

We need to evaluate what is within the parenthesis first. Also, if there were no parenthesis, we would have to calculate 6 * 7 first as multiplication comes before subtraction. Parenthesis are very necessary in infix as they can change what an expression evaluates to with removal.

The same expression however, when written in prefix does not need parenthesis:
* - 5 6 7

The order in which a prefix is calculated is always going to be conveyed by how it is arranged. All prefix expressions are calculated in the same way. To further elaborate:

With infix, finding the innermost expression to calculate first is difficult. It requires a lot of jumping around in the expression.
((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1))

But if it was written in prefix:
- * / 15 - 7 + 1 1 3 + 2 + 1 1

This prefix expression is calculated in the same way that our previous simple example (+ 2 3) is calculated. We do not even need to memorize the order of operations. Example below on what I mean.

Calculating Prefix Step by Step:
- Read from right to left
- Look for two operands and their operator and evaluate them

- * / 15 - 7 + 1 1 3 + 2 + 1 1

Now we can evaluate them:
- * / 15 - 7 + 1 1 3 + 2 2

Repeat:
- * / 15 - 7 + 1 1 3 4

Our next two operands and operators are selected again. From right to left, the two operands next to their operator will be:
- * / 15 - 7 + 1 1 3 4
(As you can see, from this example, just calculating prefix in this way does not need a knowledge of order of operations… there’s no jumping around in an expression. You just have to follow one rule)

This is what we have now:
- * / 15 - 7 2 3 4
We can see the next two to caclulate is - 7 2… and so on…
- * / 15 5 3 4
- * 3 3 4
- 9 4
And now…
The answer is 5

I wrote a program in Ruby that calculates prefix. Here’s a snippet of a part of its code (the other methods I didn’t include because I felt they were self-explanatory):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def calculate_prefix
  stack = []
  # @arg is the prefix expression
  loopSize = @arg.count
    for i in 0..loopSize
    value = @arg.pop
      if operand?(value)
        stack << value
      elsif operator?(value)
        operator1 = stack.pop
        operator2 = stack.pop
        stack << compute(value, operator1, operator2)
      end
    end
    stack.compact.first
  end

Notice I am making an array called stack. In Ruby, an array can pretty much function as a stack. In other languages, there is an actual stack datatype. Stack is a last-in-first-out data structure. You can make a Ruby implementation of a stack which RubyMonk demonstrates HERE.

Basically the last thing I push into a stack will be the first thing I can pull out. So if using a Ruby array, there are just two array methods I would use to simulate a stack. As demonstrated below.

1
2
3
4

# adding to a stack
  stack << something
# retrieving from a stack
  stack.pop

You can tell I used both of those in my calculating prefix method.

So an explanation of my method: I’m reading the prefix expression from right to left, popping a value from it. If the value is an operand, I will be pushing it onto my stack. Otherwise, if it is an operator, I’ll pop the first two elements in my stack and compute them before pushing them to the stack again.

You can tell this is a lot easier than if I were to calculate infix directly.

Prefix might not be the easiest way for me to read an expression but it makes it easier for me to deal with coding a simple calculator. It’s convenience over convention.

Reference:
https://en.wikipedia.org/wiki/Polish_notation