Start | infix2prefix
 

Prefix



Infix till prefix form fungerar lite som infix till postfix form. Skillnaden är att du reverserar det infixa uttrycket och i slutet reverserar det postfixa uttrycket.

Postfix fast baklänges

För att förstå infix till prefix -konvertering, så måste du snarare förstå infix till postfix -konvertering. Att konvertera till prefix är bara en variant av att konvertera till postfix.

infix till prefix


1. Utgår ifrån infix
2. Reversera infix -uttrycket 1
3. Konvertera till postfix 2
4. Reversera postfix

1 att tänka på här, det är att parenteserna trolgen blir spegelvända och då måste du vända dem tillbaka.
2 sånär som att när vi skall pop:a från stacken så istället för att överväga om stackens peek är större än eller lika med, så gör vi nu bara större än.




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 expr2list(txt): txt = txt.replace(" ", "") lst = re.findall(r'([a-zA-Z]|[0-9\.]+|\*|\+|\-|\/|\(|\))', txt) return(lst) def prec(c): if(c=='^'): return(3) if(c=='*' or c=='/'): return(2) if(c=='+' or c=='-'): return(1) return(0) def infix2prefix(infix): stack = [] prefix = [] infix.reverse() for i in range(len(infix)): if(infix[i]=='('): infix[i]=')' elif(infix[i]==')'): infix[i]='(' for c in infix: if(is_number(c) or c.isalpha()): prefix.append(c) elif(c=='('): stack.append('(') elif(c==')'): while(stack[len(stack)-1]!='('): prefix.append(stack[-1]) stack.pop() stack.pop() else: # skillnad mot postfix är att vid prefix enbart # prec(c) < prec(stack[-1])) while(len(stack) > 0 and prec(c) < prec(stack[-1])): prefix.append(stack[-1]) stack.pop() stack.append(c) #debug(infix,prefix,stack) while(len(stack) != 0): prefix.append(stack[-1]) stack.pop() #debug(infix,postfix,stack) prefix.reverse() return(prefix) uttryck ='((a / b) + c) - (d + (e * f ))' lst = expr2list(uttryck) prefix=infix2prefix(lst) print("uttrycket",uttryck) print("prefix notation", *prefix)
16.804933547974 ms