Entry
Language: Computer: BBCBASIC: Simple: How to convert infix to suffix? [Bracket]
Jan 9th, 2004 21:45
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 04 January 2004 - 09:23 am --------------------
Language: Computer: BBCBASIC: Simple: How to convert infix to suffix?
[Bracket]
---
Steps: Overview:
1. -Create a new BBCBASIC application
2. -Fill in the following code
--- cut here ---------------------------------------------------------
infix$ = "((2*3)^6+(4*5)+(6*7))^7"
PRINT; "infix = "; infix$
PRINT; "suffix = "; FNStringConvertInfixToSuffixS( infix$ )
PRINT
infix$ = "(3+4)*5+6-7"
PRINT; "infix = "; infix$
PRINT; FNStringConvertInfixToSuffixS( infix$ )
PRINT
infix$ = "(a+b)*c+d-e"
PRINT; "infix = "; infix$
PRINT; FNStringConvertInfixToSuffixS( infix$ )
END
:
:
:
DEF FNStringConvertInfixToSuffixS( expression$ )
token$ = "#-+*/^abcdefghijklmnopqrstuvwxyz0123456789()"
tableinput$ = "03344599999999999999999999999999999999999992"
tablestack$ = "03344599999999999999999999999999999999999929"
kstack$ = ""
stack$ = ""
kexpression$ = ""
expressionI = 1 - 1
stackI = 1 - 1
result$ = ""
posI = -1
priorityinputI = -1
prioritystackI = -1
:
stackI = stackI + 1
stack$ = "#"
I = 0
:
REPEAT
expressionI = expressionI + 1
kexpression$ = MID$( expression$, expressionI, 1 )
posI = INSTR( token$, kexpression$ )
IF posI = 0 THEN PRINT; kexpression$; " not found in token$ ";
token$ : = "error"
priorityinputI = VAL( MID$( tableinput$, posI, 1 ) )
:
kstack$ = MID$( stack$, 1, 1 )
posI = INSTR( token$, kstack$ )
IF posI = 0 THEN PRINT; kstack$; " not found in token$ "; token$ :
= "error"
prioritystackI = VAL( MID$( tablestack$, posI, 1 ) )
:
IF priorityinputI > prioritystackI THEN PROCGreater ELSE
PROCWhileSmallerOrEqual
UNTIL expressionI >= LEN( expression$ )
:
I = 1 - 1
REPEAT
I = I + 1
kstack$ = MID$( stack$, I, 1 )
IF kstack$ <> "#" AND kstack$ <> "(" AND kstack$ <> ")" THEN result$
= result$ + kstack$
UNTIL I >= LEN( stack$ )
= result$
:
DEF PROCGreater
stack$ = kexpression$ + stack$
ENDPROC
:
DEF PROCWhileSmallerOrEqual
REPEAT
kstack$ = MID$( stack$, 1, 1 )
IF kstack$ <> "(" AND kstack$ <> ")" THEN result$ = result$ + kstack$
stack$ = MID$( stack$, 2, LEN( stack$ ) - 1 )
kstack$ = MID$( stack$, 1, 1 )
posI = INSTR( token$, kstack$ )
IF posI = 0 THEN PRINT; kstack$; " not found in token$ "; token$ :
= "error"
prioritystackI = VAL( MID$( tablestack$, posI, 1 ) )
UNTIL ( priorityinputI > prioritystackI )
stack$ = kexpression$ + stack$
ENDPROC
:
--- cut here ---------------------------------------------------------
3. -Run this code
That should show:
((2*3)^6+(4*5)+(6*7))^7
resultS is 23*6^45*+67*+7^
which is respectively the infix and suffix representation.
4. -Change expressionS to your own infix string
e.g.
expressionS = "(3+4)*5+6-7"
and recompile for another example
---
Note:
In order to keep it very simple and short in this
implementation:
1. Please take spaces away.
so "(3+4)*5+6-7" is OK,
but "( 3 + 4 ) * 5 + 6 - 7" is not.
2. only single characters (like a, b, c, ..., 3, 4, 5, ...)
so "a+b*c-d^f" is OK,
but "alpha*beta+gamma" is not.
3. the priorities should here be single numbers between 0 and 9
(like 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
in your tables.
4. This program is a direct translation of the Dijkstra double
priority algorithm (see below for the link and further
description)
5. all lines in the program are single lines, so all on one line
---
---
Internet: see also:
---
Algorithm: Expression: Infix: Convert: Postfix: Overview: How convert
infix to postfix expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/26071/fid/585
----------------------------------------------------------------------
