infix till postfix
Beskrivning av hur man omvandlar ett uttryck på infix form (skriver från vänster till höger) till postfix form. Poängen med att konvertera till postfix är att postfix är enkelt evaluera.
Infix
Infix form är helt enkelt den variant vi är vana vid, där operatorerna (+ - * / osv.) står mellan operanderna (siffror, variabler).17 - 120.9 * ( 12 + 12 * 312 ) - 8 / ( 3 + 1 )
Postfix
Postfix kallas också Reverse Polish notation eller kort RPN och var ett påhitt i början av 1900-talet. Istället för parenteser ligger prioritetsordningen inbyggd i notationen.17 120.9 12 12 312 * + * - 8 3 1 + / -
Kanske är RPN mest känd bland äldre ingenjörer som kunde föredra HP's räknare som just använde denna notation. Därför finns inga parenteser på dessa räknare. Ej heller något =. Om man på en vanlig räknare måste slå 20 + 20 =, så slår man på RPN -räknare in 20 ENTER 20 + och får svaret. Mycket coolt, tyckte vissa. Kvalitet!
Poängen med postfix, i den algoritmiska världen, är att det är ganska enkelt skriva en evaluerings-algoritm som räknar ut resultatet av ett uttryck. Den logiska metoden att räkna ut infix uttryck blir alltså att först omvandla det till postfix (vilket den sidan du nu tittar på förklarar hur man gör) och därefter evaluera postfix -uttrycket.
Nedan algoritm för infix till postfix beskriver ett sätt att just omvandla den infixa notationen till en postfix -notation som bär ovanstående träds egenskaper.
Hur funkar det?
Vad algoritmen gör är att konvertera den infixa prioritetsordningen som skapas av parenteser och olika prioritet hos operatorerna - till ett uttryck där prioriterna är inbyggda i notationen. Lättaste sättet att förstå detta är att begripa hur postfix evalueras.Algoritm
Så hur konverterar vi från infix till postfix? Så, vi vandrar från token till token, med start från "17" till vänster.
17 - 120.9 * ( 12 + 12 * 312 ) - 8 / ( 3 + 1 )
Vi tänker oss också att vi dels har (1) en tom postfix -lista (där svaret skall byggas upp) och (2) en stack. Det är våra verktyg.
Sedan följer vi följande regler.
- Siffrorna hamnar i postfix.
- Operatorerna hamnar på stacken om prioriteten för operatorn (+ lägre än *) är lika eller högre än toppen på stacken, eller om stacken är tom.
- Vänsterparentes placeras alltid på stacken varefter räkningen "börjar om", dvs vänster-parentesen räknas som tom stack.
- Vid högerparentes pop:a stacken och placera i postfix.
- Om toppen på stacken har högre prioritet, pop:a elementen på stacken ett i taget och placera i postfix (sålänge prioriteten är samma eller högre på stacken).
- När inget finns kvar, pop:a stack och läggg på postfix.
Nedan exempel visar infix form, postfix form samt stacken. Vi vandrar från token till token i infix form.
Koden blir som nedan. Observera att jag använt en vanlig lista som stack.
import re
def debug(e,p,s):
exp = " ".join(e)
stk = " ".join(s)
str = " ".join(p)
print('I[{:<40}\nP[{:<40}\nS[{:<40}\n'.format(exp,str,stk));
def is_number(n):
try:
float(n)
except:
return False
return True
def prec(c):
if(c=='^'):
return(3)
if(c=='*' or c=='/'):
return(2)
if(c=='+' or c=='-'):
return(1)
return(0)
def expr2list(txt):
txt = txt.replace(" ", "")
lst = re.findall(r'([a-zA-Z]|[0-9\.]+|\*|\+|\-|\/|\(|\))', txt)
return(lst)
def infix2postfix(infix):
stack = []
postfix = []
debug("Infix","Postfix","Stack")
for c in infix:
if(is_number(c) or c.isalpha()):
postfix.append(c)
elif(c=='('):
stack.append('(')
elif(c==')'):
while(stack[len(stack)-1]!='('):
postfix.append(stack[-1])
stack.pop()
stack.pop()
else:
while(len(stack) > 0 and prec(c) <= prec(stack[-1])):
postfix.append(stack[-1])
stack.pop()
stack.append(c)
debug(infix,postfix,stack)
while(len(stack) != 0):
postfix.append(stack[-1])
stack.pop()
debug(infix,postfix,stack)
return(postfix)
uttryck = '17-120.9*(12+12*312)-8/(3+1)'
lst = expr2list(uttryck)
print(infix2postfix(lst))
Lite kommentarer till ovan kod. I python finns en funktion isnumeric() men denna funktion hanterar inte kommatecken.
def is_number(n):
try:
float(n)
except:
return False
return True
siffra='129.59'
print(siffra.isnumeric())
print(is_number(siffra))
print()
Som du ser i koden ovan kan den hantera variabler också. Det går förstås att bygga ut för att hantera logik eller vad som helst.
Titta gärna på exemplet där operatorerna s och p implementeras. De står för s = serie och p = parallell. Så man kan mata in ett elektriskt schema, även med kondensatorer och spolar.
Titta gärna på exemplet där operatorerna s och p implementeras. De står för s = serie och p = parallell. Så man kan mata in ett elektriskt schema, även med kondensatorer och spolar.