PureBoard

Code: Alles auswählen

;/ infix
;a + b * c + (d * e + f) * g
;a + b * c + d * e + f * g

;/ postfix
;a b c * + d e * f + g * +
;a b c * + d e * + f g * +

EnableExplicit

Define Infix.s = "a+b*c+(d*e+f)*g"

Define s.s{1}

Macro m_IsOperand
  s = "a" Or s = "b" Or s = "c" Or s = "d" Or s = "e" Or s = "f" Or s = "g"
EndMacro
Macro m_IsOperator
  s = "+" Or s = "*"
EndMacro

Define operand_left.s{1}
Define operand_right.s{1}
Define operator.s{1}
Define diference.l
Define ToOperatorStack.b

Procedure.l GetOperatorPriority(operator.s)
  Select operator
  Case "+" : ProcedureReturn 1
  Case "*" : ProcedureReturn 2
  EndSelect
EndProcedure

Structure Stack
  clip_level.l
  
  s.s{1}
EndStructure
NewList Stack.s{1}() ; Initialisiere Stack
NewList OperatorStack.Stack()
NewList Output.s{1}()
Define n.l, clip_level.l
For n = 1 To Len(Infix); DO Lese Postfix-Ausdruck Symbol für Symbol
  s = Mid(Infix, n, 1)
  Debug s
  If m_IsOperand ;IF nächstes Symbol ein Operand THEN
    AddElement(Stack()) : Stack() = s ;push Operand
  ElseIf s = "("
    clip_level + 1
    Debug "CKIP +1"
  ElseIf s = ")"
    clip_level - 1
    Debug "CKIP -1"
  ElseIf m_IsOperator ;IF nächstes Symbol ein Operator THEN
    Debug "OP--------"
    If CountList(Stack()) <> 0
      operand_left = Stack() : DeleteElement(Stack(), #True)
      
      AddElement(Output()) : Output() = operand_left
    Else
      operand_left = ""
    EndIf
    
    operator = s
    
    ToOperatorStack = #True
    s = Mid(Infix, n+1, 1)
    If m_IsOperand
      n + 1
      ToOperatorStack = #False
      operand_right = s
      AddElement(Output()) : Output() = operand_right
    EndIf
    
    diference = 0
    s = Mid(Infix, n+1, 1)
    If ToOperatorStack Or ( (m_IsOperator) And GetOperatorPriority(operator) < GetOperatorPriority(s) )
      AddElement(OperatorStack()) : OperatorStack()\s = operator : OperatorStack()\clip_level = clip_level
      diference + 1
    Else
      AddElement(Output()) : Output() = operator
    EndIf
    
    If CountList(OperatorStack())-diference
      SelectElement(OperatorStack(), CountList(OperatorStack())-1-diference)
      Repeat
        If OperatorStack()\clip_level = clip_level And (Not GetOperatorPriority(OperatorStack()\s) < GetOperatorPriority(s))
          Debug "AddOutputFromOp.Stack "+OperatorStack()\s+" "+Str(OperatorStack()\clip_level)+" = "+Str(clip_level)
          AddElement(Output()) : Output() = OperatorStack()\s
          DeleteElement(OperatorStack(), #True)
        Else
          Break
        EndIf
      Until PreviousElement(OperatorStack()) = 0
    EndIf
  EndIf;FI
Next ;OD

Debug "RESULT ---------------------------"

;Schlussresultat auf dem Stack
ForEach Output()
  Debug Output()
Next

Code: Alles auswählen

EnableExplicit

; Syntax in EBNF:
; Expression = Term { ['+' | '-'] Term }.
; Term = Factor { ['*' | '/'] Factor }.
; Factor = Operand | '(' Expression ')'.

Enumeration ; Symboltypen
  #Plus
  #Minus
  #Times
  #Slash
  #LParen
  #RParen
  #Operand
  #EndOfLine
EndEnumeration

Global NewList postfix.s{1}()

Global infix.s = "a + b * c + (d * e + f) * g"
Global symbol.s{1}
Global symbolType.l
Global cursorPos.l = 1

; Scanner

Procedure NextSymbol()
  While cursorPos <= Len(infix) And Mid(infix, cursorPos, 1) = " " ; Leerzeichen überspringen
    cursorPos + 1
  Wend
  
  If cursorPos > Len(infix)
    symbolType = #EndOfLine
    ProcedureReturn
  EndIf
  
  symbol = Mid(infix, cursorPos, 1)
  
  Select symbol
    Case "+": symbolType = #Plus
    Case "-": symbolType = #Minus
    Case "*": symbolType = #Times
    Case "/": symbolType = #Slash
    Case "(": symbolType = #LParen
    Case ")": symbolType = #RParen
    Default
      If Asc(symbol) >= 97 And Asc(symbol) <= 122
        symbolType = #Operand
      Else
        Debug "Ungültiges Zeichen: " + symbol
        End
      EndIf
  EndSelect
  
  cursorPos + 1
EndProcedure

; Parser

Macro Emit(op)
  AddElement(postfix())
  postfix() = op
EndMacro

Declare Expression()

Procedure Factor()
  If symbolType = #Operand
    Emit(symbol)
    NextSymbol()
  ElseIf symbolType = #LParen
    NextSymbol()
    Expression()
    
    If symbolType <> #RParen
      Debug ") erwartet an Position: " + Str(cursorPos - 1)
      End
    EndIf
    
    NextSymbol()
  Else
    Debug "Operand oder ( erwartet an Position: " + Str(cursorPos - 1)
    End
  EndIf
EndProcedure

Procedure Term()
  Define.s{1} op
  
  Factor()
  
  While symbolType = #Times Or symbolType = #Slash
    op = symbol
    
    NextSymbol()
    Factor()
    
    Emit(op)
  Wend
EndProcedure

Procedure Expression()
  Define.s op
  
  Term()
  
  While symbolType = #Plus Or symbolType = #Minus
    op = symbol
    
    NextSymbol()
    Term()
    
    Emit(op)
  Wend
EndProcedure

Procedure Parse()
  NextSymbol()
  Expression()
EndProcedure

; Test

Parse()

ForEach postfix()
  Debug postfix()
Next