basic parsing

This repo implements a calculator that reads an expression as a string and return the value of the expression as an integer.

Parsing of the string is an implementation detail of the calculator.

String parsing is implemented in two ways:

1. recursive descent parser to create an abstract syntax tree for evaluation
2. infix -> postfix parser that follows Djikstra's Shunting Yard algorithm to place expressions in reverse polish notation for evaluation

calculator := NewBasicCalculator()
calculator.Calculate("1 - 2 + 3")      //  2
calculator.Calculate("1 - ( 2 + 3 )")  // -4
calculator.Calculate("1 - ( ( 2 + 3 ) + 1 )")  // -5

The tokenizer is basic and expects that all tokenizable elements of the expression are separated by white space. any tokenizer, however, that fulfills the Tokenizer interface can be used.

type Tokenizer interface {
	HasMoreTokens() bool
	GetNextToken() *Token
}

The token specification used by the parser is limited to four distinct runes:

var specification = []TokenSpecification{
	{regex: `^(\-)?\d+`, name: NUM},
	{regex: `^[+\-]`, name: ADD_OP},
	{regex: `^\(`, name: O_PAREN},
	{regex: `^\)`, name: C_PAREN},
}

tests

To execute the tests

$ cd ./string-parser
$ go test ./... -v

References

The recursive descent parser content in this repo is inspired and guided by the Parser from Scratch course in JavaScript.