Exploration of interpreters for algebraic expressions. Inspiration came from watching Brian Harvey’s lecture about calculator, as a part of my SICP reading
Notation in which operators follow their operands e.g. 2 3 +
More examples available as tests.
Interpreter for Postfix Notation has a simple implementation with a single stack - push operands onto stack and when you encounter operator, pop 2 operands from the top of the stack and evaluate with a current operator.
Notation in which operators precede their operands e.g. + 2 3
More examples available as tests.
Stack-based implementation of interpreter for Prefix Notation requires two stacks - one for keeping track of operands and another one for operators. When we encounter operand and we already have another operand on stack, we pop it from stack, pop operator from stack and use it to evaluate current two operands.
My initial plan was to re-implement infix calculator with yacc and lex as I remember reading about it in The Unix Programming Environment book. However, this reminded me about a more modern tool, SLY which I wanted to try for a long time.
Calculator using infix notation is provided as en example in SLY documentation. Based on that I created two new parsers:
- PNCalcParser
- RPNCalcParser
that use the same Lexer. Implementation can be found towards the end of calculators.py
Fun fact: None of the so far presented implementations is related to Brian Harvey’s lecture I've mentioned at the beginning. So far, I've only focused on my approach to the calculator interpreter and it's very different from the one explained during the lecture.
One important difference is that this calculators works with Polish Notation, but expects the input to be in the form of S-expression, i.e.
(+ 2 3) instead of + 2 3.