# Shunting-Yard algorithm

## Recommended Posts

I initially created this to improve my C# understanding and what a learning curve it was. So I decided to directly translate the C# source code I had into AutoIt as a way of showing off the >Stack UDF (which you will need). Of course it can be changed not to use the Stack UDF, but why reinvent the wheel and make life even more difficult.

If you don't understand RPN or the Shunting-Yard algorithm, then please look at the links below.

```#include <StringConstants.au3>

#include "Stack.au3"

Example()

Func Example()
; Create postfix notation (RPN) from infix notation.
ConsoleWrite(StringFormat('%s: == %s', '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3', ShuntingYard_Parse('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3')) & @CRLF)
ConsoleWrite('Reference: 3 4 2 * 1 5 - 2 3 ^ ^ / +' & @CRLF)

ConsoleWrite(@CRLF); A new line.

ConsoleWrite(StringFormat('%s: == %s', '3 + 4', ShuntingYard_Parse('3 + 4')) & @CRLF)
ConsoleWrite('Reference: 3 4 +' & @CRLF)

ConsoleWrite(@CRLF); A new line.

; Expression from: http://www.slideshare.net/grahamwell/shunting-yard.

ConsoleWrite(StringFormat('%s: == %s', '2 + (3 * (8 - 4))', ShuntingYard_Parse('2 + (3 * (8 - 4))')) & @CRLF)
ConsoleWrite('Reference: 2 3 8 4 - * +' & @CRLF)

ConsoleWrite(@CRLF); A new line.

; Calculate postfix notation (RPN) examples.
ConsoleWrite('3 4 + == ' & ShuntingYard_Calculate('3 4 +') & @CRLF)
ConsoleWrite('3 4 2 * 1 5 - 2 3 ^ ^ / + == ' & ShuntingYard_Calculate('3 4 2 * 1 5 - 2 3 ^ ^ / +') & @CRLF)
ConsoleWrite('2 3 8 4 - * + == ' & ShuntingYard_Calculate('2 3 8 4 - * +') & @CRLF)
EndFunc   ;==>Example

Func ShuntingYard_Calculate(\$sExpression)
Local \$aChar = StringSplit(\$sExpression, '', \$STR_NOCOUNT), _
\$hStack = Stack(), _ ; Create a stack to push/pop to.
\$iNumber1 = 0, \$iNumber2 = 2, _
\$sDigits = '', _ ; Hold string digits e.g. in case there are numbers greater than 1 digit long.
\$sToken = '' ; Token.
For \$i = 0 To UBound(\$aChar) - 1
\$sToken = \$aChar[\$i]

If StringIsDigit(\$sToken) Then
\$sDigits &= \$sToken
ElseIf __ShuntingYard_IsOperator(\$sToken) Then
\$iNumber2 = Stack_Pop(\$hStack)
\$iNumber1 = Stack_Pop(\$hStack)
Stack_Push(\$hStack, __ShuntingYard_Eval(\$iNumber1, \$iNumber2, \$sToken))
ElseIf StringIsSpace(\$sToken) And Not (\$sDigits == '') Then
If StringIsInt(\$sDigits) Or StringIsFloat(\$sDigits) Then
\$iNumber1 = Number(\$sDigits)
Stack_Push(\$hStack, \$iNumber1)
EndIf
\$sDigits = ''
\$iNumber1 = 0
EndIf
Next
Return Stack_Pop(\$hStack)
EndFunc   ;==>ShuntingYard_Calculate

Func ShuntingYard_Parse(\$sExpression)
Local \$aChar = StringSplit(\$sExpression, '', \$STR_NOCOUNT), _
\$bIsBracket = False, _ ; Is parenthesis.
\$hStack = Stack(), _ ; Create a stack to push/pop to.
\$sOutput, _ ; Output string.
\$sToken = '' ; Token.
For \$i = 0 To UBound(\$aChar) - 1
\$sToken = \$aChar[\$i]

If StringIsDigit(\$sToken) Then ; If a digit add to the output string.
\$sOutput &= \$sToken
ElseIf __ShuntingYard_IsOperator(\$sToken) Then ; Check if a valid token.
If __ShuntingYard_IsBracket(\$sToken) Then
\$bIsBracket = \$sToken == '(' ; True if open bracket else False if closing.
If \$bIsBracket Then ; Open bracket.
Stack_Push(\$hStack, \$sToken)
Else ; Closing bracket.
\$sOutput &= ' '
Do ; Repeat until '(' is found.
\$sOutput &= Stack_Pop(\$hStack)
Until (Stack_Peek(\$hStack) == '(')
Stack_Pop(\$hStack)
EndIf
Else
\$sOutput &= " " ; Workaround for spacing and certain expressions.
If Stack_Count(\$hStack) > 0 And __ShuntingYard_HasHigherPrecedence(\$sToken, Stack_Peek(\$hStack)) Then
\$sOutput &= Stack_Pop(\$hStack)
Stack_Push(\$hStack, \$sToken)
\$sOutput &= " " ; Workaround for spacing and certain expressions.
Else
Stack_Push(\$hStack, \$sToken)
EndIf
EndIf
EndIf
Next

If Stack_Count(\$hStack) > 0 Then ; Append what is left on the stack in reverse order.
\$sOutput &= ' '
While (Stack_Count(\$hStack) > 0)
\$sOutput &= Stack_Pop(\$hStack) & ' '
WEnd
EndIf
Return \$sOutput
EndFunc   ;==>ShuntingYard_Parse

Func __ShuntingYard_Eval(\$iNumber1, \$iNumber2, \$sChar)
Switch \$sChar
Case '+'
Return \$iNumber1 + \$iNumber2

Case '-', ChrW(8722) ; Char 8722 is - but the unicode char code
Return \$iNumber1 - \$iNumber2

Case '*'
Return \$iNumber1 * \$iNumber2

Case '/'
Return \$iNumber1 / \$iNumber2

Case '^'
Return \$iNumber1 ^ \$iNumber2

Case Else
Return \$iNumber1

EndSwitch
EndFunc   ;==>__ShuntingYard_Eval

Func __ShuntingYard_HasHigherPrecedence(\$sChar1, \$sChar2)
Local \$iChar1 = __ShuntingYard_PrecendenceValue(\$sChar1), _
\$iChar2 = __ShuntingYard_PrecendenceValue(\$sChar2)
If \$iChar1 = 0 And \$iChar2 = 0 Then
Return False
EndIf
Return \$iChar1 <= \$iChar2 And Not (\$sChar1 == '^')
EndFunc   ;==>__ShuntingYard_HasHigherPrecedence

Func __ShuntingYard_IsBracket(\$sChar)
Return \$sChar == '(' Or \$sChar == ')'
EndFunc   ;==>__ShuntingYard_IsBracket

Func __ShuntingYard_IsOperator(\$sChar)
Return \$sChar == '+' Or \$sChar == '-' Or \$sChar == ChrW(8722) Or \$sChar == '*' Or \$sChar == '/' Or \$sChar == '^' Or \$sChar == '(' Or \$sChar == ')'; Char 8722 is - but the unicode char code.
EndFunc   ;==>__ShuntingYard_IsOperator

Func __ShuntingYard_PrecendenceValue(\$sChar)
Switch \$sChar
Case '+', '-'
Return 2

Case '*', '/'
Return 3

Case '^'
Return 4

Case Else
Return 0
EndSwitch
EndFunc   ;==>__ShuntingYard_PrecendenceValue```
Edited by guinness
##### Share on other sites
• 2 weeks later...
• 4 months later...

## Create an account

Register a new account

• ### Similar Content

• hi everyone!
I need some help with my rpn calculator.
I first translated it from vbscript to autoitscript and that's when i stumbled on problem one:
(46) : ==> Array variable has incorrect number of subscripts or subscript dimension range exceeded.:
\$Stack[ubound(\$Stack)] = \$Item
^ ERROR
After that (and i know this from testing it as a vbscript) it can't work with negative numbers:
"1 - - 2" to Reverse Polish notation = "1 - 2 -" gives me the build in error...

Can you guy's help me with my code pleas?
Func Print(\$what,\$er = 0) \$t = '' if \$err <> 0 then \$t = 'ERROR!' MsgBox(\$er,\$st,\$what) EndFunc Func RPN(\$Tokenarray) Local \$Stack = [] Local \$Result Local \$Operator_B Local \$Operator_A For \$Token = 0 To Ubound(\$Tokenarray) If Isoperator(\$Tokenarray[\$Token]) Then \$Operator_B = Pop(\$Stack) \$Operator_A = Pop(\$Stack) If \$Operator_A = "" Then Print("The user has not input sufficient values in the expression.",16) exit EndIf Switch \$Tokenarray[\$Token] Case "+" \$Result = Number(\$Operator_A,3) + Number(\$Operator_B,3) Case "-" \$Result = Number(\$Operator_A,3) - Number(\$Operator_B,3) Case "*" \$Result = Number(\$Operator_A,3) * Number(\$Operator_B,3) Case "/" \$Result = Number(\$Operator_A,3) / Number(\$Operator_B,3) Case "^" \$Result = Number(\$Operator_A,3) ^ Number(\$Operator_B,3) EndSwitch Push(\$Result,\$Stack) Else Push(\$Tokenarray[\$Token],\$Stack) EndIf Next If Ubound(\$Stack) > 1 Then Print("The user input has too many values.",16) Exit EndIf Return pop(\$Stack) EndFunc Func Push(\$Item, Byref \$Stack) If Ubound(\$Stack) > -1 Then Redim \$Stack[Ubound(\$Stack) + 1] \$Stack[Ubound(\$Stack)] = \$Item Else Local \$Stack = [\$Item] EndIf EndFunc Func Pop(\$Stack) \$pop = "" If Ubound(\$Stack) > -1 Then \$Pop = \$Stack[Ubound(\$Stack)] Redim \$Stack[Ubound(\$Stack) - 1] EndIf Return \$pop EndFunc Func Peek(\$Stack) \$peek = "" If Ubound(\$Stack) > -1 Then \$Peek = \$Stack(Ubound(\$Stack)) EndIf Return \$peek EndFunc Func Isoperator(\$Operator) Return StringInstr("+-*/^&<=>", \$Operator) <> 0 And StringLen(\$Operator) = 1 EndFunc Func Precedence(\$Operator) If Isoperator(\$Operator) Then Switch \$Operator case "^" Return 4 case "*","/" Return 3 case "+","-" Return 2 case "&" Return 1 case "<","=",">" Return 0 EndSwitch EndIf EndFunc ;################################################################################################## ; (4 - -5) = (4|-|-|5) = (4|-|5|-) ; input tokens rpn Global \$calculate_this = ["4","-","5","-"] Print(rpn(\$calculate_this)) thanks in advance ,
TheAutomator

• Reverse Polish Notation (RPN) is a math notation in which each operator follows its two operands. I own an HP 48G calculator which uses RPN, and when I tried to use the windows calculator I had so much trouble that I wrote my own calculator. Basically, it has a stack of numbers; any time an operator is pressed, that operation is carried out immediately on the two items on the bottom of the stack, or the stack and the input if there is anything in the input. This method reduces the requirements for parenthesis and makes calculating equations/functions relatively easy: instead of
(sqrt(5+8))/(8*9)
you would enter
5 ENTER 8 + SQRT 8 ENTER 9 * /

Practical implications

calc2.au3
×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...