Kifejezések kiértékelése Go nyelven

A Programozás Wiki wikiből

Először definiáljuk a típusokat.

types.go:

package types

type Operand float
type Operator byte
type Bracket bool // '(': true, ')': false

func Vegrehajt(a, b Operand, op Operator) Operand {
    switch(byte(op)) {
        case '+':
            return Operand(float(a)+float(b))
        case '-':
            return Operand(float(a)-float(b))
        case '*':
            return Operand(float(a)*float(b))
        case '/':
            return Operand(float(a)/float(b))
    }
    return Operand(0)    // hogy a fordito is boldog legyen
}

Vegrehajt függvény értelemszerűen kiszámol egy egyszerű kifejezést.

Ezek után nézzük meg, hogyan lehet megvalósítani a lengyel formára alakítást.

lengyel.go:

package lengyel

import "./queue"
import "./stack"
import "strconv"
import . "./types"

Először is egy string-t kell olyan formára alakítani, amit az algoritmus könnyen tud kezelni. Ezt valósítja meg a format függvény, melynek bemenete egy string kimenete pedig egy sor, ami a lengyel formára hozás algoritmusának bemeneti sora lesz.

func format(str string) *queue.Queue {
    form := queue.NewQueue()
    n := len(str)
    for i:=0; i<n; i++ {
        switch str[i] {
        case '(':        form.In(Bracket(true))
        case ')':        form.In(Bracket(false))
        case '+','-','*','/':    form.In(Operator(str[i]))
        case ' ': break
        default:
            j := i
            ok := func(o byte) bool {
                return (o>47 && o<58) || o==46
            }
            for i++; (i<n && ok(str[i])); i++ {
                ;
            }
            if (i<n && !ok(str[i])) || i == n {
                i--
            }
            f,_ := strconv.Atof(str[j:i+1])
            form.In(Operand(f))
        }
    }
    return form
}

Prioritást vizsgáló függvény:

func prior(op Operator) int {
    switch op {
        case '+', '-':
            return 1
        default:    // '*' '/'
            return 2
    }
    return 0
}

Ezek után az algoritmus implementációja:

// operadns: [0-9]+(\.[0-9])?[0-9]*
// operators: [*/+-]
// brackets: [()]
// space: [ ]
func LengyelForma(str string) *queue.Queue {
    O := queue.NewQueue()
    I := format(str)
    V := stack.NewStack()

    for !I.IsEmpty() {
        x,_ := I.Out()
        switch x.(type) {
        case Operator:
            _x := x.(Operator)
            val,_ := V.Top()
            b,isBracket := val.(Bracket)
            o,isOperator := val.(Operator)
            for (!V.IsEmpty()) && ( ( (isBracket && !bool(b)) || !isBracket) && ((isOperator && (prior(o) >= prior(_x))) || !isOperator)) {
                y,_ := V.Pop()
                O.In(y)
            }
            V.Push(x)
        case Operand:
            O.In(x)
        case Bracket:
            _x,_ := x.(Bracket)
            if bool(_x) {
                V.Push(_x)
            } else {
                val,_ := V.Pop()
                y,isBracket := val.(Bracket)
                for ((isBracket && !bool(y)) || !isBracket) {
                    O.In(val)
                    val,_ = V.Pop()
                    y,isBracket = val.(Bracket)
                }
            }
        }
    }
    for !V.IsEmpty() {
        y,_ := V.Pop()
        O.In(y)
    }
    return O
}

Ezzel kész van a kifejezés lengyel formára hozása. A kiértékelő függvény:

kiert.go:

package kiert

import . "./types"
import "./queue"
import "./stack"

func Kiertekel(I *queue.Queue) float {
    V := stack.NewStack()

    for !I.IsEmpty() {
        x,_ := I.Out()
        switch x.(type) {
            case Operand:
                V.Push(x)
            case Operator:
                v1,_ := V.Pop()
                v2,_ := V.Pop()
                a,_ := v1.(Operand)
                b,_ := v2.(Operand)
                op,_:=x.(Operator)
                V.Push(Vegrehajt(a,b,op))
        }
    }
    f,_ := V.Pop()
    ret,_ := f.(Operand)
    return float(ret)
}

Ez már egy float típust ad vissza, ez a kifejezésünk értéke.

Ezek használatára egy egyszerű példa:

main.go:

package main

import "./lengyel"
import "./kiert"
import "fmt"

func main() {
    I := lengyel.LengyelForma("12 + ( 34 + 45 ) * ( 67 - 89 )")
    ertek := kiert.Kiertekel(I)
   
    fmt.Printf("eredmény: %f\n",ertek)

}

Ez csak az algoritmus implementációja. Mit ahogy az algorimus sem foglalkozik a bemeneti kifejezések helyességével, ez a program sem. Ezt a helyességet, általában egy lexikális elemző szokta ellenőrizni.