Kifejezések kiértékelése
Innen: Programozás Wiki
(Kifejezés-kiértékelése szócikkből átirányítva)
Ugrás a navigációhozUgrás a kereséshezKifejezé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.