Sitter för kul och leker i assembler och försökte göra en infix till postfix-konverterare för att sedan kunna evaluera aritmetiska uttryck.
Med infix till postfix menar jag alltså t.ex, (2+3)*2 => 23+2* (för tydlighetens skull: 2,3+2*).
Den kan bara hantera tal från 0 till 9.
Receptet för detta fick jag på en föreläsning i Datorsystem I och jag har inte möjlighet att prata med honom föränn senare nästa vecka så jag tänkte se ifall det va någon här som sysslat med detta förut eller så.
Receptet ser ut som följer:
1. Kolla nästa indata
2. Om operand (variabel/konst): Skriv ut
3. Om "(": push
4. Om operator
Om TOS (top of stack) är "(" : push
Om högre precedens än TOS har: push *
Annars skriv ut och åter till 1
5. Om ")": pop till dess att "(" dyker upp
6. Om mer indata finns: åter till 1
7. Om indata slut: pop resterande
Subrutinen ska alltså ta en pekare till en sträng och returnera en pekare till en ny sträng.
Har fått en version som fungerar enligt receptet ovan men det blir fel och jag misstänker att det är fel vid den rad markerad med *.
Ta följande sträng (1+2)*(3+4).
Enligt receptet får vi 12+3+4* vilket blir 6 * 4 = 24.
Rätt borde vara 12+34+* vilket blir 37* vilket är 3 * 7 = 21. Korrekt.
Alltså något fel i receptet.
Jag misstänker att raden markerad med * och nästföljande rad borde vara något i stil med:
Om det förekommer en operator på stacken med högre precedens innan (om) det förekommer en "(" : Skriv ut
Annars: push, åter till 1.
Jag är dock lite osäker. Någon som förstår mitt problem och kan sätta sej in i det och till och med se felet i receptet?
Lite halvjobbigt att göra detta direkt (rakt upp och ned) i asm. Men å andra sidan är stackhantering detsamma som postfix... och strängen du har en pekare till är ju i infix, vilket ger att ditt problem ligger i prioriteter (paranteser och * samt /) när du vandrar igenom strängen.
En CFG för att hantera prioriteter och konvertera infix till postfix kan se ut så här
(fr Drakboken: "Compilers: Principles, Techniques and Tools")
e -> t f
t -> + f t | $
f -> f' t'
t' -> * f' t' | $
f' -> ( e ) | 0 .. 9
Så a*b+c ska bli ab*c+ och a*(b+c) ska bli abc+*, vilket motsvarar i pseudoasm:
Jag kom på varför det blev fel. Iom att stacken i assembler växer ner åt så tänkte jag TOS som det först inlagda elementet när det egentligen ska ses som det senast inlagda elementet.
