Kifejezések kiértékelése

Kifejezések kiértékelésére sokféle algoritmust lehet írni. A legelterjedtebb módszer azonban az, ha egy kifejezést először lengyel formára alakítunk, majd egy egyszerű, vermet használó algoritmussal ezt kiértékeljük.

Lássuk a lengyel formára alakítás algoritmusát:

Ehhez most formálisan két sort, és egy vermet használunk.

I : input sor
O : output sor
V : verem

while not I.IsEnd()
    x := I.Out()
    if x = '('
        V.Push(x)
    else-if x is Operand
        O.In(x)
    else-if x is Operator
        while (not V.IsEnd()) and (V.Top() /= '(') and (Prior(V.Top()) >= Prior(x))
            y := V.Pop()
            O.In(y)
        end while
        V.Push(x)
    else-if x = ')'
        y := V.Pop()
        while y /= '('
            O.In(y)
            V.Pop(y)
    end if
end while
while not V.IsEnd()
    y := V.Pop()
    O.In(y)
end while

Most O sorban található a lengyel formára alakított kifejezés.

Prior() függvény, egy operátor prioritását adja vissza. Pl: +: 1, *: 2, ^: 3, stb...

Ennek kiértékelése:

I: input sor (előző algoritmusban kapott O sor)
V: verem

while not I.IsEmpty()
    x := I.Out()
    if x is Operandus
        V.Push(x)
    else-if x is Operator
        a := V.Pop()
        b := V.Pop()
        V.Push( Vegrehajt(a,x,b)) )
    end if
end while
x := V.Pop()
return x

retrun x utasítás adja vissza, a kifejezésünk értékét. Implementálásnál nem szabad elfelejteni, hogy ez az algoritmus nem foglalkozik egy kifejezés helyességével.

Az algoritmus megvalósítása különböző nyelveken

Go