Building Replicalc Part 2: The Calculator
With my development environment set up, I began working on an initial version for Linux.
The first step was to build a tokenizer, which takes an expression like
100 + 200 and identifies the individual tokens: 100,
+, and 200. This will allow the calculator to distinguish between
numbers and operators.
I already had a good idea of how to tackle this using a stack of strings, with each element representing an individual token. By iterating over each character in the expression, we can check whether it's the same "type" of character as the previous. If they're the same (for example, if both are numeric), append the new character to the top-most element of the stack. If they are different, push the new character onto the stack, where it will form a new token. There might be better ways to tackle it, but this was intuitive.
The only area that proved a bit tricky was handling negative numbers. Depending on context,
the - character can be either an operator (subtract), or it can indicate a
negative number. To determine whether the context makes it an operator or not, I simply
check the characters adjacent to it: if the previous character was a symbol and the next
character is a number, then the - character is part of the following number;
otherwise it's the subtract operator.
The next step was to convert expressions from infix (3 + 5 * 4) to postfix
(3 5 4 * +). Postfix expressions can be evaluated from left-to-right using a
stack, making it the ideal notation for a calculator. This is usually achieved through the
shunting yard algorithm,
which juggles ("shunts") the expression's numbers and operators between two stacks
until they are re-arranged in postfix notation. This was straightforward to implement
using the detailed outline from Wikipedia.
Next, it was time to build the heart of the calculator: the evaluator, which calculates the result of postfix expressions. Once again, I had a pretty good idea of how to achieve this. By iterating over the expression's tokens, we can check whether each one is a number or an operator. If it's a number, we add it to a stack. If it's an operator, we pop the last two numbers from the stack and apply the operator to them. The whole expression can be processed from start to finish in this way.
At this point, I had a working calculator for Linux. The final part was the user interface. So far, I had simply hardcoded a handful of test expressions, which were then evaluated and printed to the console so I could check the result - but a real calculator needs to be interactive. I considered the options and decided to use ncurses, since it makes it easy to support editing one's input using the backspace, left, and right keys. Although ncurses doesn't support MS-DOS, I figured I could develop a close enough alternative later using a combination of conio.h and Open Watcom's graph.h.
And with that, the Linux version was done. The next step was to get the calculator running on MS-DOS.