Shunting yard algoritmus - 2. díl vlastní kalkulačky

Go

Možností, jak zpracovat vstupní tokeny ve správném pořadí, je hned několik. Jedním z nejznámějších algoritmů pro zpracování matematických výrazů je Shunting Yard algoritmus. Ten je pojmenován po seřaďovacím nádraží, protože rovněž přesouvá tokeny mezi třemi "kolejemi".

Shunting yard algoritmus - 2. díl vlastní kalkulačky

Article in English can be found on dev.to/arxeiss/shunting-yard-parser-expression-calculator-cik

Tento článek patří do seriálu Vlastní kalkulačka s výrazy. Ostatní články seriálu:


Výstupem lexikální analýzy z minulého dílu je seznam tokenů, což je jen přeformátovaný vstup. Stále není vyřešen problém závorek ani priority a asociativity operátorů. A přesně to je úkol parseru. Výstupem ale není konkrétní hodnota, nýbrž taková datová struktura, kterou lze jednoduše evaluovat. Například proměnné jsou v této struktuře stále zastoupeny pouze svým názvem. Je tedy možné evaluaci provádět i opakovaně jen s jinými vstupními hodnotami.

Zmíněný algoritmus Shunting Yard nejčastěji převádí infixovou notaci na Reverzní polskou notací, známou též jako postfixová notace. Mezi její nevýhody ale patří nemožnost spolehlivě rozeznat binární a unární operátory + a -. Nebo rozpoznat počet argumentů, které funkce přijímá, protože RPN vůbec nepoužívá závorky. Proto moje implementace převádí vstup přímo do Abstraktního syntaktického stromu, u kterého tyto problémy odpadají.

Algoritmus níže je velmi zjednodušený, kompletní implementace včetně komentářů a ukázkového kódu je opět dostupná na github.com/arxeiss/go-expression-calculator

Parser - Shunting Yard

Algoritmus Shunting Yard vynalezl E. Dijkstra a inspiroval se seřaďovacím nářadím. Protože celý průběh je pouze o přemisťování tokenů mezi vstupní frontou, zásobníkem operátorů a výstupní frontou či zásobníkem. Implementace níže produkuje AST, který se tvoří ve výstupním zásobníku.

func (p *Parser) Parse(tokenList []*lexer.Token) (ast.Node, error) {
	output := make([]ast.Node, 0)
	opStack := make([]*lexer.Token, 0)
	var err error

tokenLoop:
	for i := 0; i < len(tokenList); i++ {
		curToken := tokenList[i]
		switch curToken.Type() {
		case lexer.Number:
			// if the token is a number, then: push it to the output queue
			output = append(output, ast.NumericNode(curToken.Value()))
case lexer.Identifier: // if the token is a function then: push it onto the operator stack if tokenList[i+1].Type() == lexer.LPar { // Expecting the identifier is function name, because is followed by ( opStack = append(opStack, tokenList[i]) } else { // if the token is a variable name, then: push it to the output queue. output = append(output, ast.VariableNode(tokenList[i].Identifier())) }
case lexer.Addition, lexer.Substraction, lexer.Exponent, lexer.Multiplication, lexer.Division, lexer.FloorDiv, lexer.Modulus: // if the token is an operator then: while there is an operator at the top of the operator stack for len(opStack) > 0 { topStackEl := opStack[len(opStack)-1] if topStackEl.Type() == lexer.LPar { break } // If the operator at the top of the operator stack has greater precedence // OR // The operator at the top of the operator stack has equal precedence AND the token is left associative if p.priorities.GetPrecedence(topStackEl.Type()) > p.priorities.GetPrecedence(curToken.Type()) || (p.priorities.GetPrecedence(topStackEl.Type()) == p.priorities.GetPrecedence(curToken.Type()) && p.priorities.GetAssociativity(curToken.Type()) == parser.LeftAssociativity) { // pop operators from the operator stack onto the output queue output, err = p.addToOutput(output, topStackEl) opStack = opStack[:len(opStack)-1] continue } break } // push token onto the operator stack opStack = append(opStack, curToken)
case lexer.LPar: // if the token is a left parenthesis, then: push it onto the operator stack opStack = append(opStack, curToken)
case lexer.RPar: // if the token is a right parenthesis, then: // while the operator at the top of the operator stack is not a left parenthesis: for len(opStack) > 0 { topStackEl := opStack[len(opStack)-1] if topStackEl.Type() == lexer.LPar { break } // pop the operator from the operator stack onto the output queue. output, err = p.addToOutput(output, topStackEl) opStack = opStack[:len(opStack)-1] } // if there is a left parenthesis at the top of the operator stack, then: // pop the operator from the operator stack and discard it opStack = opStack[:len(opStack)-1] // if there is a function token at the top of the operator stack, then: // pop the function from the operator stack onto the output queue. if opStack[len(opStack)-1].Type() == lexer.Identifier { output, err = p.addToOutput(output, opStack[len(opStack)-1]) opStack = opStack[:len(opStack)-1] } } if err != nil { return nil, err } } // while there are still operator tokens on the stack for len(opStack) > 0 { // pop the operator from the operator stack onto the output queue topStackEl := opStack[len(opStack)-1] output, err = p.addToOutput(output, topStackEl) opStack = opStack[:len(opStack)-1] } return opStack, err }
// addToOutput is converting nodes in output list into a AST
func (p *Parser) addToOutput(output []ast.Node, token *lexer.Token) ([]ast.Node, error) { var op ast.Operation switch t := token.Type(); t { case lexer.UnaryAddition, lexer.UnarySubstraction: output[len(output)-1] = ast.NewUnaryNode(t, output[len(output)-1]) case lexer.Addition, lexer.Substraction, lexer.Multiplication, lexer.Division, lexer.Exponent, lexer.FloorDiv, lexer.Modulus: r := output[len(output)-1] l := output[len(output)-2] output = output[:len(output)-1] output[len(output)-1] = ast.NewBinaryNode(t, l, r) case lexer.Identifier: // Current functions support only 1 parameter output[len(output)-1] = ast.NewFunctionNode(token.Identifier(), output[len(output)-1]) } return output, nil }

Úpravy algoritmu a možná rozšíření

Algoritmus výše vychází z pseudokódu na anglické Wikipedii, který ale nebude plně fungovat pro vstupy jako 5 9 88 nebo ++/*--*+/66. Nekontroluje totiž, jestli se po tokenu čísla nebo proměnné nachází operátor a naopak. Nezvládá také zpracovat unární operátory + a - nebo funkce s proměnným počtem parametrů.

První dva problémy jsou vyřešené pomocí proměnné expect. Tato stavová proměnná se přepíná mezi stavy ExpectOperand a ExpectOperator a kontroluje, zda se zpracovává token správného typu. Rozšíření je detailněji popsané na StackOverflow a pomocí této metody lze také rozšířit algoritmus a přidat podporu pro unární operátory.

Rozšíření algoritmu a přidání podpory pro proměnný počet argumentů funkce bude popsáno v jednom z dalších dílů seriálu.


S názory na článek nebo algoritmus samotný se můžete podělit v komentářích

Přidat komentář

Položky označené * jsou povinné. Email nebude zveřejněn

Buď první, kdo přidá komentář. Zatím zde nic není