Anonymous user
Parsing/Shunting-yard algorithm: Difference between revisions
no edit summary
(Add shunting yard implementation in OCaml) |
No edit summary |
||
Line 3,818:
postfix:3 4 2 * 1 5 - 2 3^ ^ / +
</pre>
=={{header|XOJO}}==
{{trans|VBA}}
<lang XOJO>
Function ShuntingYard(strInfix As String) As String
Dim i as Integer
Dim token, tokenArray() As String
Dim stack(), queue() As Variant
Dim discard As String
Dim op1, op2 As String
Dim Left_Brackets, Right_Brackets As Integer
Dim output As String
Dim dbl_output As Double
Left_Brackets = CountFields(strInfix, "(")
Right_Brackets = CountFields(strInfix, ")")
If Left_Brackets = Right_Brackets Then
'Get tokens
tokenArray = Split(strInfix," ")
'Initialize array (removed later)
ReDim stack(1)
ReDim queue(1)
'Loop over tokens
For i = 0 to tokenArray.Ubound
'i = i + 1
If i > UBound(tokenArray) Then
Exit For
Else
token = tokenArray(i ) 'i-1 due to Split returning a Base 0
End If
If token = "" Then
Exit For
End If
Dim stackString As String
Dim queuString As String
for m as Integer = 0 to stack.Ubound
stackString = stackString + " " + stack(m)
Next
for m as Integer = 0 to queue.Ubound
queuString = queuString + " " + queue(m)
Next
MsgBox(Str(i) + " " + token + " " + stackString + " " + queuString)
'Window1.txtQueu.Text = Window1.txtQueu.Text + Str(i) + " " + token + " " + stackString + " " + queuString + EndOfLIne
' If-loop over tokens (either brackets, operators, or numbers)
If token = "(" Then
stack.Append(token)
ElseIf token = ")" Then
While stack(stack.Ubound) <> "("
queue.Append(stack.pop)
Wend
discard = stack.Pop 'discard "("
ElseIf isOperator(token) Then
op1 = token
//Do While (isOperator(Peek(stack)))
While isOperator( stack(stack.Ubound) ) = True
op2 = stack(stack.Ubound)
If op2 <> "^" And precedence(op1) = precedence(op2) Then
'"^" is the only right-associative operator
queue.Append(stack.pop)
ElseIf precedence(op1) < precedence(op2) Then
queue.Append(stack.Pop)
Else
Exit While
End If
Wend
//Loop
stack.Append(op1)
Else 'number
'actually, wrong operator could end up here, like say %
'If the token is a number, then add it to the output queue.
queue.Append(CStr(token))
End If
Next
for i = 0 to queue.Ubound
output = output +queue(i) + " "
next
for i = stack.Ubound DownTo 0
output = output + stack(i)+" "
next
While InStr(output, " ") <> 0
output = ReplaceAll(output," "," ")
Wend
output = Trim(output)
Return output
Else
MsgBox("Syntax Error!" + EndOfLine + "Count left brackets: " + Str(Left_Brackets) + EndOfLine +"Count right brackets: " + Str(Right_Brackets))
End If
End Function
Function isOperator(op As String) As Boolean
If InStr("+-*/^", op) <> 0 and Len(op) = 1 Then
Return True
End If
End Function
Function precedence(op As String) As Integer
If isOperator(op) = True Then
If op = "+" or op = "-" Then
Return 2
ElseIf op = "/" or op = "*" Then
Return 3
ElseIf op = "^" Then
Return 4
End If
End If
End Function</lang>
{{out}}
<pre>?ShuntingYard("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
0 3
1 + 3
2 4 + 3
3 * + 3 4
4 2 + * 3 4
5 / + * 3 4 2
6 ( + / 3 4 2 *
7 1 + / ( 3 4 2 *
8 - + / ( 3 4 2 * 1
9 5 + / ( - 3 4 2 * 1
10 ) + / ( - 3 4 2 * 1 5
11 ^ + / 3 4 2 * 1 5 -
12 2 + / ^ 3 4 2 * 1 5 -
13 ^ + / ^ 3 4 2 * 1 5 - 2
14 3 + / ^ ^ 3 4 2 * 1 5 - 2
Output:
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
| |||