Parser - Anfang ist getan wie weiter machen?

faxe1008 · 21. März 2014, 20:19

Hi,

ich habe vor langer Zeit mal an einem Parser rumgebaut und das Projekt nun wieder herausgekramt. So weit hab ich ihn nun:

Spoiler anzeigen

Visual Basic-Quellcode

Public Class Parser
Public Token_List As New List(Of String)
Private Function NewSplit(ByVal sen As String, ByVal splitter As Char()) As List(Of String)
Dim final_list As New List(Of String)
Dim last_found As Integer = 0
For u = 0 To sen.Length - 1
For Each Chr As Char In splitter
If Char.Parse(sen(u)) = Chr Then
final_list.Add(sen.Substring(last_found, u - last_found))
final_list.Add(sen(u))
last_found = u + 1
End If
Next
Next
If last_found < sen.Length Then
final_list.Add(sen.Substring(last_found, sen.Length - last_found))
End If
Return final_list
End Function
Private Function SolveMinusProblem(ByVal liste As List(Of String)) As List(Of String)
If liste(0) = "-" AndAlso IsNumeric(liste(1)) Then
liste(1) = "-" + liste(1)
liste.RemoveAt(0)
End If
For i As Integer = 1 To liste.Count - 1
If i < liste.Count AndAlso i - 1 < liste.Count Then
If liste(i) = "-" AndAlso IsNumeric(liste(i - 1)) = False Then
liste(i + 1) = "-" + liste(i + 1)
liste.RemoveAt(i)
liste.Remove("")
End If
End If
Next
Return liste
End Function
Public Function Eval(ByVal expression As String) As Double
Token_List = SolveMinusProblem(NewSplit(expression, {"^"c, "/"c, "*"c, "+"c, "-"c, "("c, ")"c}))
Token_List = DeleteEmpty(Token_List)
While Token_List.Count > 1
While Contains(Token_List, "^", True)
Dim opindex As Integer = GetIndex(Token_List, "^")
Token_List(opindex) = Math.Pow(Double.Parse(Token_List(opindex - 1)), Double.Parse(Token_List(opindex + 1))).ToString
Token_List.RemoveAt(opindex - 1)
Token_List.RemoveAt(opindex)
Token_List = DeletEmptyBrackets(Token_List)
End While
While Contains(Token_List, "/", True)
Dim opindex As Integer = GetIndex(Token_List, "/")
Token_List(opindex) = (Double.Parse(Token_List(opindex - 1)) / Double.Parse(Token_List(opindex + 1))).ToString
Token_List.RemoveAt(opindex - 1)
Token_List.RemoveAt(opindex)
Token_List = DeletEmptyBrackets(Token_List)
End While
While Contains(Token_List, "*", True)
Dim opindex As Integer = GetIndex(Token_List, "*")
Token_List(opindex) = (Double.Parse(Token_List(opindex - 1)) * Double.Parse(Token_List(opindex + 1))).ToString
Token_List.RemoveAt(opindex - 1)
Token_List.RemoveAt(opindex)
Token_List = DeletEmptyBrackets(Token_List)
End While
While Contains(Token_List, "-", True)
Dim opindex As Integer = GetIndex(Token_List, "-")
Token_List(opindex) = (Double.Parse(Token_List(opindex - 1)) - Double.Parse(Token_List(opindex + 1))).ToString
Token_List.RemoveAt(opindex - 1)
Token_List.RemoveAt(opindex)
Token_List = DeletEmptyBrackets(Token_List)
End While
While Contains(Token_List, "+", True)
Dim opindex As Integer = GetIndex(Token_List, "+")
Token_List(opindex) = (Double.Parse(Token_List(opindex - 1)) + Double.Parse(Token_List(opindex + 1))).ToString
Token_List.RemoveAt(opindex - 1)
Token_List.RemoveAt(opindex)
Token_List = DeletEmptyBrackets(Token_List)
End While
End While
Return Double.Parse(Token_List.ElementAt(0))
End Function
Private Function Contains(ByVal liste As List(Of String), ByVal search As String, ByVal isoperator As Boolean) As Boolean
Dim re = False
For u = 0 To liste.Count - 1
If liste(u) = search AndAlso isoperator AndAlso IsNumeric(liste(u - 1)) AndAlso IsNumeric(liste(u + 1)) Then re = True
If liste(u) = search AndAlso isoperator = False AndAlso IsNumeric(liste(u + 1)) AndAlso liste(u + 2) = ")" Then re = True
Next
Return re
End Function
Private Function GetIndex(ByVal liste As List(Of String), ByVal search As String) As Integer
For u = 0 To liste.Count - 1
If search = liste(u) Then Return u
Next
End Function
Private Function DeletEmptyBrackets(ByVal liste As List(Of String)) As List(Of String)
While Contains(liste, "(", False)
Dim brackopen As Integer = GetIndex(liste, "(")
If IsNumeric(liste(brackopen + 1)) AndAlso liste(brackopen + 2) = ")" Then
liste.RemoveAt(brackopen)
liste.RemoveAt(brackopen + 1)
End If
End While
Return liste
End Function
Private Function DeleteEmpty(ByVal liste As List(Of String)) As List(Of String)
While liste.Contains("")
liste.Remove("")
End While
Return liste
End Function
End Class

Das funktioniert soweit auch gut - bis eben mehrere Klammern ins Spiel kommen. Hier mal das Grundgerüst:

Spoiler anzeigen

VB.NET-Quellcode

Public Class Parser
Public Token_List As New List(Of String)
Private Function NewSplit(ByVal sen As String, ByVal splitter As Char()) As List(Of String)
Dim final_list As New List(Of String)
Dim last_found As Integer = 0
For u = 0 To sen.Length - 1
For Each Chr As Char In splitter
If Char.Parse(sen(u)) = Chr Then
final_list.Add(sen.Substring(last_found, u - last_found))
final_list.Add(sen(u))
last_found = u + 1
End If
Next
Next
If last_found < sen.Length Then
final_list.Add(sen.Substring(last_found, sen.Length - last_found))
End If
Return final_list
End Function
Private Function SolveMinusProblem(ByVal liste As List(Of String)) As List(Of String)
If liste(0) = "-" AndAlso IsNumeric(liste(1)) Then
liste(1) = "-" + liste(1)
liste.RemoveAt(0)
End If
For i As Integer = 1 To liste.Count - 1
If i < liste.Count AndAlso i - 1 < liste.Count Then
If liste(i) = "-" AndAlso IsNumeric(liste(i - 1)) = False Then
liste(i + 1) = "-" + liste(i + 1)
liste.RemoveAt(i)
liste.Remove("")
End If
End If
Next
Return liste
End Function
Public Function Eval(ByVal expression As String) As Double
Token_List = SolveMinusProblem(NewSplit(expression, {"^"c, "/"c, "*"c, "+"c, "-"c, "("c, ")"c}))
Token_List = DeleteEmpty(Token_List)
End Function
Private Function Contains(ByVal liste As List(Of String), ByVal search As String, ByVal isoperator As Boolean) As Boolean
Dim re = False
For u = 0 To liste.Count - 1
If liste(u) = search AndAlso isoperator AndAlso IsNumeric(liste(u - 1)) AndAlso IsNumeric(liste(u + 1)) Then re = True
If liste(u) = search AndAlso isoperator = False AndAlso IsNumeric(liste(u + 1)) AndAlso liste(u + 2) = ")" Then re = True
Next
Return re
End Function
Private Function GetIndex(ByVal liste As List(Of String), ByVal search As String) As Integer
For u = 0 To liste.Count - 1
If search = liste(u) Then Return u
Next
End Function
Private Function DeletEmptyBrackets(ByVal liste As List(Of String)) As List(Of String)
While Contains(liste, "(", False)
Dim brackopen As Integer = GetIndex(liste, "(")
If IsNumeric(liste(brackopen + 1)) AndAlso liste(brackopen + 2) = ")" Then
liste.RemoveAt(brackopen)
liste.RemoveAt(brackopen + 1)
End If
End While
Return liste
End Function
Private Function DeleteEmpty(ByVal liste As List(Of String)) As List(Of String)
While liste.Contains("")
liste.Remove("")
End While
Return liste
End Function
End Class

NewSplit befüllt die Tokenlist mit den einzelnen Zahlen, Operatoren. SolveMinusProblem schiebt zum Beispiel bei 12*-1 das Minus und die 1 in ein Token. Durch die NewSplit-Function entstehen Leerzeichen die durch die Function DeleteEmpty gelöscht werden.

Soviel zu dem aktuellen Stand. Wie kann ich nun weitermachen ohne allzuviel an der bisherigen Grundstruktur herumzufummeln ? Danke für eure Hilfe :thumbup:

Artentus · 21. März 2014, 20:27

Klammern sind nur sehr schwer zu handhaben, am ehesten müsste man sowas wohl rekursiv lösen.
Aber warum wehrst du dich denn gegen ShuntingYard? Ist richtig einfach zu implementieren (die Vorgehensweise ist exakt spezifiziert), lässt Klammern verschwinden und die Auswertung besteht dann nur noch darin, nen Stack zu durchlaufen. Da du die Tokens ja schon gefiltert hast, ist der Rest dann nur noch Firlefanz.

faxe1008 · 21. März 2014, 20:34

@Artentus
Offengestanden, weil ich nicht wirklich verstanden habe wie die Function Infix zu Postfix schreiben soll.... Außerdem hab ich mir die Frage gestellt, ob man zwangsläufig eine extra Klasse Token (=> List(of Token))entwerfen muss, oder ob man das auch mit einer List(of String) regeln könnte.

Artentus · 21. März 2014, 20:54

faxe1008 schrieb:

ob man das auch mit einer List(of String) regeln könnte

Kannst du auch - wenn du einen großen SelectCase-Block am Ende haben willst.

Der Algo ist eigentlich gar nicht so kompliziert. Eingabe ist die Liste der Tokens in Infix-Notation, Ausgabe soll eine Liste der Tokens in Postfix-Notation sein.
Vereinfacht passiert dann das:
Alle Tokens werden der Reihe nach durchgegangen. Eine Zahl wird sofort zur Ausgabe hinzugefügt, denn an der Reihenfolge, in der die Zahlen in der Postfix-Notation im Vergleich zur Infix-Notation auftauchen, ändert sich nichts, steht in der Eingabe a vor b, dann muss auch in der Ausgabe a vor b stehen.
Ist der Token ein Operator, passiert die Magie. Zunächst wird nachgesehen, ob auf dem Operatorstack ein Operator vorhanden ist. Ist einer vorhanden und besitzt dieser eine höhere Priorität, als der aktuelle Operator (Assoziativität wird hier auch noch berücksichtigt), so wird dieser vom Operatorstack entfernt und zur Ausgabe hinzugefügt, denn je höher die Priorität, desto früher muss der Operator natürlich ausgeführt werden. Dieser Schritt wird solange wiederholt, bis die Bedingung nicht mehr erfüllt ist. Dann wird der aktuelle Operator selbst auf den Stack geschoben und landet damit vor allen verbleibenden Operatoren mit niedrigerer Priorität, so wies sein soll.
Ganz am Ende des Algorithmuses müssen noch alle auf dem Stack verbleibenden Operatoren zur Ausgabe hinzugefügt werden, was ja logisch ist, weil sie sonst einfach unterschlagen werden würden.
Wenn Funktionen und Klammern dazukommen, wirds nochmal etwas komplizierter, aber ich hoffe, ich hab das einigermaßen verständlich rübergebracht.

faxe1008 · 21. März 2014, 21:04

Für die Priorität würde sich ein Dictionary(String, Integer) anbieten oder?
Jetzt noch zum konvertieren. Nehmen wir mal an der Term 2+18/3-7 vor. Dann müsste ich deiner Anweisung nach die Liste so editieren:
2 ; + ; 18 ; / ; 3 ; - ; 7
=> 2 ; 18 ; + ; 3 ; / ; 7; -
=> 2 ; 18 ; / ; 3 ; + ; 7 ; -

oder nicht? Falls das passt wie wäre die Vorgehensweise von Schritt 2 zu 3 ?

Artentus · 21. März 2014, 21:30

Dieser Schritt zwei wird mit ShuntingYard niemals erreicht, es geht gleich von eins nach drei, ist nämlich einfacher. Der Dritte Schritt ist übrigens nicht korrekt.

Hier mal Schritt für Schritt:

Spoiler anzeigen

Jetzt liegt eine korrekte Postfix-Notation der Tokens vor. Gelöst wird jetzt wie folgt (es wird ein Augabestack benötigt, nicht mit dem Operatorstack verwechseln):

Spoiler anzeigen

faxe1008 · 22. März 2014, 13:29

@Artentus
So, habe nun mich an einer Infix zu Postfix Funktion versucht...:

Spoiler anzeigen

VB.NET-Quellcode

Private Function Infix2Postfix(ByVal liste As List(Of String)) As List(Of String)
Dim ausgabestack As New List(Of String)
Dim operatorstack As New List(Of String)
For Each token As String In liste
If IsNumeric(token) Then ausgabestack.Add(token)
If IsNumeric(token) = False Then operatorstack.Add(token)
If operatorstack.Count - 1 > 0 AndAlso IsNumeric(token) Then
If operatorstack.Count > 1 Then
operatorstack = SortStackAfterPriority(operatorstack)
ausgabestack.Add(operatorstack(operatorstack.Count - 1))
operatorstack.RemoveAt(operatorstack.Count - 1)
End If
End If
Next
Return ausgabestack
End Function
Public Function SortStackAfterPriority(ByVal liste As List(Of String)) As List(Of String)
Dim gabe As New List(Of String)
While liste.Contains("+")
gabe.Add("+")
liste.Remove("+")
End While
While liste.Contains("-")
gabe.Add("-")
liste.Remove("-")
End While
While liste.Contains("/")
gabe.Add("/")
liste.Remove("/")
End While
While liste.Contains("*")
gabe.Add("*")
liste.Remove("*")
End While
While liste.Contains("^")
gabe.Add("^")
liste.Remove("^")
End While
Return gabe
End Function

2+18/3-7
=> 2 ; 18 ; 3 ; / ; 7 ; -

Das Plus wird leider verschluckt.

Artentus · 22. März 2014, 15:08

Der Operatorstack sollte schon ein Stack sein, dann kann auch diese unnötige Sortier-Funktion weg.

RodFromGermany · 23. März 2014, 12:05

Artentus schrieb:

Klammern sind nur sehr schwer zu handhaben

@ faxe1008
Du musst zu einer öffnenden Klammer die kommunizierende schließende Klammer finden.
Dabei wird es passieren, dass Du dabei beliebig viele weitere öffnende Klammern und auch schließende Klammern findest, die musst Du dann von innen nach außen auflösen.
Das ist mühselig, aber effizient machbar.

faxe1008 · 23. März 2014, 12:16

@Artentus
Hi,

hab das ganze auch nochmal mit Stack versucht (läuft leider nicht):

Spoiler anzeigen

Allerdings hänge ich ein wenig an dem Verständnis, wann aus dem Operatorstack auf den Ausgabestack geschoben wird ?(. Und wie kann ich den Opstack effizient sortieren lassen?

RushDen · 23. März 2014, 13:17

Zu der Sache mit den Klammern:
Das mit den Klammern hab ich so gemacht, dass ich ab dem index der ersten gefundenen Klammer zusätzlich eine Variable anzahlKlammern gemacht habe und immer wenn eine "(" klammer gefunden wurde, wird die variable hochgezählt, wenn eine ")" wird sie runtergezählt, wenn die Variable nun 0 erreicht hat hat man den Index der schliessenden Klammer und kann den Ausdruck mit substring rausholen und die Parse funktion mit dem Ausdruck rekursiv aufrufen (also so mach ich das, ka ob dir das hilft, weil ich habs ohne stack undson zeug gemacht)

faxe1008 · 23. März 2014, 14:34

Ohne dir nahetreten zu wollen, ich möchte das mal effizient mit ShuntingYard lösen können, zumindest einfache Ausdrücke ohne Klammern (vorerst

).

RushDen · 23. März 2014, 14:51

Ja machs so wie du's für richtig hälst, sollte ja nur ein Vorschlag sein

Artentus · 23. März 2014, 15:11

faxe1008 schrieb:

wie kann ich den Opstack effizient sortieren lassen

Der muss doch gar nicht sortiert werden, bei einer korrekten Umsetzung des Algorithmus ist der ja automatisch sortiert.

Ich hab dir mal ne stark vereinfachte Version des Algos geschrieben:

Spoiler anzeigen

VB.NET-Quellcode

Public NotInheritable Class Token
Private Enum TokenType
Number
[Operator]
End Enum
Private Enum Associativity
Left
Right
End Enum
Private Const NumberName As String = "<Number>"
Private Shared ReadOnly OperatorList() As String
Private Shared ReadOnly Actions As Dictionary(Of String, Action(Of Stack(Of Double)))
Private Shared ReadOnly Priorities As Dictionary(Of String, Integer)
Private Shared ReadOnly Associativities As Dictionary(Of String, Associativity)
Shared Sub New()
OperatorList = {"!", "+", "-", "*", "/", "^"}
Actions = New Dictionary(Of String, Action(Of Stack(Of Double)))()
Actions.Add("!", Sub(stack) stack.Push(-stack.Pop()))
Actions.Add("+", Sub(stack) stack.Push(stack.Pop() + stack.Pop()))
Actions.Add("-", Sub(stack) stack.Push(-stack.Pop() + stack.Pop()))
Actions.Add("*", Sub(stack) stack.Push(stack.Pop() * stack.Pop()))
Actions.Add("/", Sub(stack) stack.Push((1 / stack.Pop()) * stack.Pop()))
Actions.Add("^", Sub(stack)
Dim exponent = stack.Pop()
stack.Push(Math.Pow(stack.Pop(), exponent))
End Sub)
Priorities = New Dictionary(Of String, Integer)()
Priorities.Add(NumberName, Integer.MaxValue)
Priorities.Add("!", 0)
Priorities.Add("+", 1)
Priorities.Add("-", 1)
Priorities.Add("*", 2)
Priorities.Add("/", 2)
Priorities.Add("^", 3)
Associativities = New Dictionary(Of String, Associativity)()
Associativities.Add(NumberName, Associativity.Left)
Associativities.Add("!", Associativity.Left)
Associativities.Add("+", Associativity.Left)
Associativities.Add("-", Associativity.Left)
Associativities.Add("*", Associativity.Left)
Associativities.Add("/", Associativity.Left)
Associativities.Add("^", Associativity.Right)
End Sub
Private ReadOnly _name As String
Private ReadOnly _type As TokenType
Private ReadOnly _value As Double
Public Sub New(value As String)
If OperatorList.Contains(value) Then
_name = value
_type = TokenType.Operator
_value = 0
ElseIf Double.TryParse(value, _value) Then
_name = NumberName
_type = TokenType.Number
Else
Throw New ArgumentException("The specified value is not a valid token.")
End If
End Sub
Public Function EvaluatesBefore(other As Token) As Boolean
Dim thisPriority = Priorities(Me._name)
Dim otherPriority = Priorities(other._name)
Return thisPriority > otherPriority OrElse (thisPriority = otherPriority AndAlso Associativities(Me._name) = Associativity.Left)
End Function
Public Sub Eval(stack As Stack(Of Double))
Select Case _type
Case TokenType.Number
stack.Push(_value)
Case TokenType.Operator
Actions(_name).Invoke(stack)
End Select
End Sub
Public Overrides Function ToString() As String
Select Case _type
Case TokenType.Number
Return _value.ToString()
Case TokenType.Operator
Return _name
Case Else
Return String.Empty
End Select
End Function
Public Shared Widening Operator CType(value As String) As Token
Return New Token(value)
End Operator
End Class
Public Shared Function ShuntingYardBasic(inputList As IEnumerable(Of Token)) As Token()
Dim outputList As New List(Of Token)
Dim operatorStack As New Stack(Of Token)
For Each token In inputList
Do While operatorStack.Count > 0 AndAlso operatorStack.Peek().EvaluatesBefore(token)
outputList.Add(operatorStack.Pop())
Loop
operatorStack.Push(token)
Next
Do While operatorStack.Count > 0
outputList.Add(operatorStack.Pop())
Loop
Return outputList.ToArray()
End Function
Public Shared Function EvalPostfixTokens(postfixTokens As IEnumerable(Of Token)) As Double
Dim stack As New Stack(Of Double)
For Each token In postfixTokens
token.Eval(stack)
Next
Return stack.Pop()
End Function

Anwendung dann z.B. so:

VB.NET-Quellcode

Dim tokens() As Token = {"2", "+", "18", "/", "3", "-", "7"}
Dim postfixTokens() As Token = ShuntingYardBasic(tokens)
Dim result As Double = EvalPostfixTokens(postfixTokens)
MessageBox.Show(result.ToString())

RodFromGermany · 24. März 2014, 07:31

RushDen schrieb:

wenn eine ")" wird sie runtergezählt, wenn die Variable nun 0 erreicht hat hat man

Glück, wenn die Syntax stimmt.
Du musst Dich davon überzeugen, dass zu jeder öffnenden Klammer die kommunizierende schließende Klammer da ist.
Ansonsten ist es richtig:
Finde die erste öffnende Klammer, finde die zu dieser öffnenden die kommunizierende schließende Klammer und parse diesen Ausdruck so lange, bis alle Klammern aufgelöst sind, dann Du haben feddich.

ErfinderDesRades · 24. März 2014, 09:31

mag zwar funktionieren, ist aber glaub viel mühsamer zu coden, und ist weniger effizient als der Shunting-Yard-Algo.

RushDen · 24. März 2014, 14:28

@RodFromGermany
Dann fragst du ab, wenn man am Ende des Ausdrucks angelangt ist und anzahlKlammern > 0 ist, fehlt die schliessende Klammer und du wirfst eine exception

Mag sein dass es mühsamer ist, habs aber aus eigener Überlegung so gemacht

RodFromGermany · 24. März 2014, 14:47

RushDen schrieb:

exception

Ich habe mir angewöhnt, vom Schlecht-Fall auszugehen, da fährt man letztenendes bequemer.

faxe1008 · 1. April 2014, 15:23

@Artentus
So habe mit deinen Ideen mal an meiner Version rumgebastelt:

Spoiler anzeigen

VB.NET-Quellcode

Public Class Parser
Public Token_List As New List(Of String)
#Region "preparing-functions"
Private Function NewSplit(ByVal sen As String, ByVal splitter As Char()) As List(Of String)
Dim final_list As New List(Of String)
Dim last_found As Integer = 0
For u = 0 To sen.Length - 1
For Each Chr As Char In splitter
If Char.Parse(sen(u)) = Chr Then
final_list.Add(sen.Substring(last_found, u - last_found))
final_list.Add(sen(u))
last_found = u + 1
End If
Next
Next
If last_found < sen.Length Then
final_list.Add(sen.Substring(last_found, sen.Length - last_found))
End If
Return final_list
End Function
Private Function SolveMinusProblem(ByVal liste As List(Of String)) As List(Of String)
If liste(0) = "-" AndAlso IsNumeric(liste(1)) Then
liste(1) = "-" + liste(1)
liste.RemoveAt(0)
End If
For i As Integer = 1 To liste.Count - 1
If i < liste.Count AndAlso i - 1 < liste.Count Then
If liste(i) = "-" AndAlso IsNumeric(liste(i - 1)) = False Then
liste(i + 1) = "-" + liste(i + 1)
liste.RemoveAt(i)
liste.Remove("")
End If
End If
Next
Return liste
End Function
Private Function DeleteEmpty(ByVal liste As List(Of String)) As List(Of String)
While liste.Contains("")
liste.Remove("")
End While
Return liste
End Function
#End Region
Public Function Eval(ByVal expr As String) As String
Token_List = SolveMinusProblem(NewSplit(expr, {"^"c, "/"c, "*"c, "+"c, "-"c, "("c, ")"c}))
Token_List = DeleteEmpty(Token_List)
Token_List = ShuntingYardBasic(Token_List)
Dim str = String.Join(" ; ", Token_List)
Return str
End Function
Public Function ShuntingYardBasic(inputList As List(Of String)) As List(Of String)
Dim outputList As New List(Of String)
Dim operatorStack As New Stack(Of String)
For Each token As String In inputList
If IsNumeric(token) Then
outputList.Add(token)
End If
If operatorStack.Count = 0 AndAlso IsNumeric(token) = False Then
operatorStack.Push(token)
Continue For
End If
If operatorStack.Count > 0 AndAlso IsNumeric(token) = False Then
If IsHigher(operatorStack.Peek, token) Then
outputList.Add(operatorStack.Pop)
operatorStack.Push(token)
End If
End If
Next
While operatorStack.Count > 0
outputList.Add(operatorStack.Pop)
End While
Return outputList
End Function
Public Enum Associt
Left
Right
End Enum
Function IsHigher(ByVal older As String, ByVal newer As String) As Boolean
Dim Priority As New Dictionary(Of String, Integer)
Priority.Add("+", 0)
Priority.Add("-", 0)
Priority.Add("*", 1)
Priority.Add("/", 1)
Priority.Add("^", 2)
Dim Associativity As New Dictionary(Of String, Associt)
Associativity.Add("+", Associt.Left)
Associativity.Add("-", Associt.Left)
Associativity.Add("*", Associt.Left)
Associativity.Add("/", Associt.Left)
Associativity.Add("^", Associt.Right)
Return Priority(older) > Priority(newer) OrElse (Priority(older) = Priority(newer) AndAlso Associativity(newer) = Associt.Left)
End Function
End Class

Zu Testzwecken gibt Eval nen String zurück. Ausdrücke wie 2*4/4+3 parst er schon richtig :thumbsup:

, allerdings kommt er bei 3+4*2 ins Schleudern und gibt

3 ; 4 ; 2 ; +

zurück. Es muss eine Kleinigkeit sein die hier nicht stimmt, aber ich weiß nicht was. Wäre nett wenn jemand den Fehler findet und erklärt :thumbup:

EDIT//: Hab den Fehler gefunden :thumbup:

:

Quellcode

Public Function ShuntingYardBasic(inputList As List(Of String)) As List(Of String)
Dim outputList As New List(Of String)
Dim operatorStack As New Stack(Of String)
For Each token As String In inputList
If IsNumeric(token) Then
outputList.Add(token)
End If
If operatorStack.Count = 0 AndAlso IsNumeric(token) = False Then
operatorStack.Push(token)
Continue For
End If
If operatorStack.Count > 0 AndAlso IsNumeric(token) = False Then
If IsHigher(operatorStack.Peek, token) Then
outputList.Add(operatorStack.Pop)
operatorStack.Push(token)
Else
operatorStack.Push(token)
End If
End If
Next
While operatorStack.Count > 0
outputList.Add(operatorStack.Pop)
End While
Return outputList
End Function

Artentus · 1. April 2014, 17:25

Du machst es dir unnötig schwer, wenn du auf die Token-Klasse verzichtest, nur so am Rande.

Parser - Anfang ist getan wie weiter machen?

Parser - Anfang ist getan wie weiter machen?

Visual Basic-Quellcode

VB.NET-Quellcode

faxe1008 schrieb:

VB.NET-Quellcode

Artentus schrieb:

Quellcode

faxe1008 schrieb:

VB.NET-Quellcode

VB.NET-Quellcode

RushDen schrieb:

RushDen schrieb:

VB.NET-Quellcode

Quellcode

Tags

Ähnliche Themen

5 Benutzer haben hier geschrieben