Parsing/Shunting-yard algorithm: Difference between revisions
Content added Content deleted
(Add Nim) |
|||
| Line 4,710: | Line 4,710: | ||
15 3 +,/,^,^ 3,4,2,*,1,5,-,2 |
15 3 +,/,^,^ 3,4,2,*,1,5,-,2 |
||
Output: |
Output: |
||
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
{{trans|C#}} |
|||
<lang vbnet>Module Module1 |
|||
Class SymbolType |
|||
Public ReadOnly symbol As String |
|||
Public ReadOnly precedence As Integer |
|||
Public ReadOnly rightAssociative As Boolean |
|||
Public Sub New(symbol As String, precedence As Integer, rightAssociative As Boolean) |
|||
Me.symbol = symbol |
|||
Me.precedence = precedence |
|||
Me.rightAssociative = rightAssociative |
|||
End Sub |
|||
End Class |
|||
ReadOnly Operators As Dictionary(Of String, SymbolType) = New Dictionary(Of String, SymbolType) From |
|||
{ |
|||
{"^", New SymbolType("^", 4, True)}, |
|||
{"*", New SymbolType("*", 3, False)}, |
|||
{"/", New SymbolType("/", 3, False)}, |
|||
{"+", New SymbolType("+", 2, False)}, |
|||
{"-", New SymbolType("-", 2, False)} |
|||
} |
|||
Function ToPostfix(infix As String) As String |
|||
Dim tokens = infix.Split(" ") |
|||
Dim stack As New Stack(Of String) |
|||
Dim output As New List(Of String) |
|||
Dim Print = Sub(action As String) Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {String.Join(" ", stack.Reverse())} ]", $"out[ {String.Join(" ", output)} ]") |
|||
For Each token In tokens |
|||
Dim iv As Integer |
|||
Dim op1 As SymbolType |
|||
Dim op2 As SymbolType |
|||
If Integer.TryParse(token, iv) Then |
|||
output.Add(token) |
|||
Print(token) |
|||
ElseIf Operators.TryGetValue(token, op1) Then |
|||
While stack.Count > 0 AndAlso Operators.TryGetValue(stack.Peek(), op2) |
|||
Dim c = op1.precedence.CompareTo(op2.precedence) |
|||
If c < 0 OrElse Not op1.rightAssociative AndAlso c <= 0 Then |
|||
output.Add(stack.Pop()) |
|||
Else |
|||
Exit While |
|||
End If |
|||
End While |
|||
stack.Push(token) |
|||
Print(token) |
|||
ElseIf token = "(" Then |
|||
stack.Push(token) |
|||
Print(token) |
|||
ElseIf token = ")" Then |
|||
Dim top = "" |
|||
While stack.Count > 0 |
|||
top = stack.Pop() |
|||
If top <> "(" Then |
|||
output.Add(top) |
|||
Else |
|||
Exit While |
|||
End If |
|||
End While |
|||
If top <> "(" Then |
|||
Throw New ArgumentException("No matching left parenthesis.") |
|||
End If |
|||
Print(token) |
|||
End If |
|||
Next |
|||
While stack.Count > 0 |
|||
Dim top = stack.Pop() |
|||
If Not Operators.ContainsKey(top) Then |
|||
Throw New ArgumentException("No matching right parenthesis.") |
|||
End If |
|||
output.Add(top) |
|||
End While |
|||
Print("pop") |
|||
Return String.Join(" ", output) |
|||
End Function |
|||
Sub Main() |
|||
Dim infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
|||
Console.WriteLine(ToPostfix(infix)) |
|||
End Sub |
|||
End Module</lang> |
|||
{{out}} |
|||
<pre>3: stack[ ] out[ 3 ] |
|||
+: stack[ + ] out[ 3 ] |
|||
4: stack[ + ] out[ 3 4 ] |
|||
*: stack[ + * ] out[ 3 4 ] |
|||
2: stack[ + * ] out[ 3 4 2 ] |
|||
/: stack[ + / ] out[ 3 4 2 * ] |
|||
(: stack[ + / ( ] out[ 3 4 2 * ] |
|||
1: stack[ + / ( ] out[ 3 4 2 * 1 ] |
|||
-: stack[ + / ( - ] out[ 3 4 2 * 1 ] |
|||
5: stack[ + / ( - ] out[ 3 4 2 * 1 5 ] |
|||
): stack[ + / ] out[ 3 4 2 * 1 5 - ] |
|||
^: stack[ + / ^ ] out[ 3 4 2 * 1 5 - ] |
|||
2: stack[ + / ^ ] out[ 3 4 2 * 1 5 - 2 ] |
|||
^: stack[ + / ^ ^ ] out[ 3 4 2 * 1 5 - 2 ] |
|||
3: stack[ + / ^ ^ ] out[ 3 4 2 * 1 5 - 2 3 ] |
|||
pop: stack[ ] out[ 3 4 2 * 1 5 - 2 3 ^ ^ / + ] |
|||
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre> |
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre> |
||
| Line 4,830: | Line 4,934: | ||
postfix:3 4 2 * 1 5 - 2 3^ ^ / + |
postfix:3 4 2 * 1 5 - 2 3^ ^ / + |
||
</pre> |
</pre> |
||
=={{header|Xojo}}== |
=={{header|Xojo}}== |
||