In this module, we build a complete useful program: a calculator. More than that, it will be a calculator which uses polish postfix notation! Sounds impressive huh!?
Actually, back in the very early days of calculators, polish postfix notation was used instead of the modern notation, which we call infix notation. The reason for the polish? As you are about to find out, it is simple to program. Computers love polish postfix!
Also in this module you will learn about some very important programming concepts, including linked lists, stacks and program flow.top
Most people are familiar with the meaning of the infix statement 2+3*(5-7)/2 = -1. However, it looks quite different in polish postfix notation. The word postfix indicates that the arithmetic operations form a postfix, i.e. come after, the numbers in the expression.
The above expression can be written 2 3 5 7 - 2 / * + in polish postfix. The best way to think about this notation is to keep a running tally of what has happened so far in the calculation. Firstly the numbers 2, 3, 5, 7 are entered. Next the minus operates on the last two numbers present, i.e. the 5 and 7. The total of that calculation is -2 and this value replaces the 5 and 7 so that the running tally reads 2 3 -2. Next a further 2 is read in so that we have 2 3 -2 2. Now a divide operates on the last two values and replaces them with the result, leaving a running tally of 2 3 -1. Now a multiply operates on the last two numbers and replaces them, leaving 2 -3. Finally an addition operates on the only two remaining numbers leaving a result of -1.
As you can see, a program to evaluate an expression provided in polish notation must have a number of features. It must be able to perform arithmetic operations. It must have somewhere to store numbers that are entered. It must keep track of the result of the last operation that was performed. Finally, it must check that numbers are actually present to operate on when an arithmetic operation is encountered.
The key to programming all of this efficiently turns out to be the data structure used to store the numbers being entered. The structure that works best is known as a stack. For now it is sufficient to know that a stack is precisely what it sounds like. It is a pile of things, like a stack of papers, such that the last thing onto the pile is the first thing that comes off the pile. This is easy to see in the polish example above. It is the last two numbers present, that are taken and operated on first whenever an arithmetic operator is encountered.
But before we develop a stack in C, we need to discuss how to make a linked list. And before we can do that, we need to know about pointers.