Jump to content

Shunting Yard With Functions?


Recommended Posts

Hi everyone ;)

Learned a lot about programming languages and how they work the last days :)

In my previous post I had a question about RPN calculators and how they evaluate unary symbols,

now i have a question about the Shunting Yard algorithm  :D

The script I'll post here has 2 bugs in it, the firs one is a nasty small bug that i can't trace..

The last "push(pop(stack),queue)" call always pushes a "0" to the stack and I don't know why.

edit: [gray text solved by JohnOne]

The second problem:

I don't know if I did this right but I wanted to modify this algorithm to work with functions as well.

here is the pseudo-code explanation that i followed: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

did I do this right?

Because at the moment the algorithm allows wrong usage of "(" and ")"

example: function((10,20,)30) is allowed but it is clearly not the right way to call a function..

#INCLUDE <ARRAY.AU3>

FUNC MSG($WHAT)
    IF ISARRAY($WHAT) THEN
        MSGBOX(0,"ARRAY",_ARRAYTOSTRING($WHAT))
    ELSE
        MSGBOX(64,"MESSAGE",$WHAT)
    ENDIF
ENDFUNC

FUNC PUSH($ITEM, BYREF $STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    IF $UBOUND > 0 THEN
        REDIM $STACK[$UBOUND + 1]
        $STACK[$UBOUND] = $ITEM
    ELSE
        DIM $STACK[] = [$ITEM]
    ENDIF
ENDFUNC

FUNC PEEK($STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    IF $UBOUND > 0 THEN
        RETURN $STACK[$UBOUND - 1]
    ENDIF
ENDFUNC

FUNC POP(BYREF $STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    LOCAL $RETURN
    IF $UBOUND > 0 THEN
        $RETURN = $STACK[$UBOUND - 1]
        REDIM $STACK[$UBOUND - 1]
    ENDIF
ENDFUNC

FUNC STACKISEMPTY($STACK)
    IF UBOUND($STACK) > 0 THEN
        RETURN FALSE
    ELSE
        RETURN TRUE
    ENDIF
ENDFUNC

FUNC ASSOCIATIVITY($OPERATOR)
    IF $OPERATOR = "^" THEN
        RETURN "RIGHT"
    ELSE
        RETURN "LEFT"
    ENDIF
ENDFUNC

FUNC PRECEDENCE($OPERATOR)
    SWITCH $OPERATOR
        CASE "^"
            RETURN 3
        CASE "*","/"
            RETURN 2
        CASE ELSE
            RETURN 1
    ENDSWITCH
ENDFUNC

FUNC ISOPERATOR($OPERATOR)
    RETURN STRINGINSTR("+-*/^",$OPERATOR) <> 0
ENDFUNC

;###################################################################################################
FUNC SHUNTINGYARD($INPUT)

    Local $queue[0]
    Local $stack[0]
    Local $token, $operator_a, $operator_b

    For $token = 0 To UBound($input) - 1
        Switch $input[$token]
            Case "("
                push($input[$token], $stack)

            Case ")"
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching ""("".")
                WEnd
                POP($stack)

            Case ","
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching function ""("".")
                WEnd

            Case "+","-","*","/","^"
                $operator_a = $input[$token]
                While isoperator(peek($stack))
                    $operator_b = peek($stack)
                    if (associativity($operator_b) = "LEFT" and precedence($operator_a) = precedence($operator_b)) or (precedence($operator_a) < precedence($operator_b)) then
                        push(pop($stack), $queue)
                    Else
                        ExitLoop
                    EndIf
                WEnd
                push($operator_a, $stack)

            Case "function"
                push("function", $stack)

            Case Else
                push($input[$token], $queue)

        EndSwitch
    Next

    for $itemcount = 0 to ubound($stack) - 1
        if peek($stack) = "(" then msg("can't find a matching "")"".")
        push(pop($stack), $queue)
    next

    Return $queue

ENDFUNC
;###################################################################################################
GLOBAL $input = ["function","(","1",",","2",")"]

msg($input)
$shuntingYard = shuntingyard($input)

msg($shuntingYard)
;###################################################################################################

any help would be appreciated!

TheAutomator

Edited by TheAutomator
Link to comment
Share on other sites

Now you can consult my signature.

UDF List:

 
_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_ArrayFilter/_ArrayReduce_BinaryBin()_CheckMsgBox()_CmdLineRaw()_ContextMenu()_ConvertLHWebColor()/_ConvertSHWebColor()_DesktopDimensions()_DisplayPassword()_DotNet_Load()/_DotNet_Unload()_Fibonacci()_FileCompare()_FileCompareContents()_FileNameByHandle()_FilePrefix/SRE()_FindInFile()_GetBackgroundColor()/_SetBackgroundColor()_GetConrolID()_GetCtrlClass()_GetDirectoryFormat()_GetDriveMediaType()_GetFilename()/_GetFilenameExt()_GetHardwareID()_GetIP()_GetIP_Country()_GetOSLanguage()_GetSavedSource()_GetStringSize()_GetSystemPaths()_GetURLImage()_GIFImage()_GoogleWeather()_GUICtrlCreateGroup()_GUICtrlListBox_CreateArray()_GUICtrlListView_CreateArray()_GUICtrlListView_SaveCSV()_GUICtrlListView_SaveHTML()_GUICtrlListView_SaveTxt()_GUICtrlListView_SaveXML()_GUICtrlMenu_Recent()_GUICtrlMenu_SetItemImage()_GUICtrlTreeView_CreateArray()_GUIDisable()_GUIImageList_SetIconFromHandle()_GUIRegisterMsg()_GUISetIcon()_Icon_Clear()/_Icon_Set()_IdleTime()_InetGet()_InetGetGUI()_InetGetProgress()_IPDetails()_IsFileOlder()_IsGUID()_IsHex()_IsPalindrome()_IsRegKey()_IsStringRegExp()_IsSystemDrive()_IsUPX()_IsValidType()_IsWebColor()_Language()_Log()_MicrosoftInternetConnectivity()_MSDNDataType()_PathFull/GetRelative/Split()_PathSplitEx()_PrintFromArray()_ProgressSetMarquee()_ReDim()_RockPaperScissors()/_RockPaperScissorsLizardSpock()_ScrollingCredits_SelfDelete()_SelfRename()_SelfUpdate()_SendTo()_ShellAll()_ShellFile()_ShellFolder()_SingletonHWID()_SingletonPID()_Startup()_StringCompact()_StringIsValid()_StringRegExpMetaCharacters()_StringReplaceWholeWord()_StringStripChars()_Temperature()_TrialPeriod()_UKToUSDate()/_USToUKDate()_WinAPI_Create_CTL_CODE()_WinAPI_CreateGUID()_WMIDateStringToDate()/_DateToWMIDateString()Au3 script parsingAutoIt SearchAutoIt3 PortableAutoIt3WrapperToPragmaAutoItWinGetTitle()/AutoItWinSetTitle()CodingDirToHTML5FileInstallrFileReadLastChars()GeoIP databaseGUI - Only Close ButtonGUI ExamplesGUICtrlDeleteImage()GUICtrlGetBkColor()GUICtrlGetStyle()GUIEventsGUIGetBkColor()Int_Parse() & Int_TryParse()IsISBN()LockFile()Mapping CtrlIDsOOP in AutoItParseHeadersToSciTE()PasswordValidPasteBinPosts Per DayPreExpandProtect GlobalsQueue()Resource UpdateResourcesExSciTE JumpSettings INISHELLHOOKShunting-YardSignature CreatorStack()Stopwatch()StringAddLF()/StringStripLF()StringEOLToCRLF()VSCROLLWM_COPYDATAMore Examples...

Updated: 22/04/2018

Link to comment
Share on other sites

Now you can consult my signature.

 

Hi guinness  :)

Your udf can work with numbers and operators only, no function support there..

Or are you talking about the stack functions?

edit:

Forgot to mention that i got the shunting-yart function working perfectly without the "function" modification..

Edited by TheAutomator
Link to comment
Share on other sites

What is"$RETURN = $STACK[$UBOUND - 1]" in your POP function?

 

Nice, thanks  :thumbsup:

should be:

FUNC POP(BYREF $STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    LOCAL $RETURN
    IF $UBOUND > 0 THEN
        $RETURN = $STACK[$UBOUND - 1]
        REDIM $STACK[$UBOUND - 1]
        RETURN $RETURN
    ENDIF
ENDFUNC

Guess I deleted that line by accident while modifying the function..

Edited by TheAutomator
Link to comment
Share on other sites

To be clear, the first problem (solved) doesn't solve the second problem.

The pseudo-code part on Wikipedia that describes how to handle function arguments:

  • If the token is a function token, then push it onto the stack.
  • If the token is a function argument separator (e.g., a comma):
  • If the token is a right parenthesis:
  •     Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
  •     Pop the left parenthesis from the stack, but not onto the output queue.
  •     If the token at the top of the stack is a function token, pop it onto the output queue.
  •     If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

 

my code parts:

Case "function"
    push("function", $stack)

Case ","
    While Not(peek($stack) = "(")
        push(pop($stack), $queue)
        If stackisempty($stack) Then msg("Can't find a matching function ""("".")
    WEnd

Case ")"
    While Not(peek($stack) = "(")
        push(pop($stack), $queue)
        If stackisempty($stack) Then msg("Can't find a matching ""("".")
    WEnd
    POP($stack)

;If the token at the top of the stack is a function token, pop it onto the output queue.
    ;(this line is done by "Case "function" i guess?"
Edited by TheAutomator
Link to comment
Share on other sites

update:

found out that a lot of people have trouble with the function modification in this algorithm.  :(

On Wikipedia they are not very clear about it to.

I even helped a guy finding a bug in his java evaluator project while explaining my problem...

so far I made it detect a misplaced "","" or ""("":

FUNC SHUNTINGYARD($INPUT)

    Local $queue[0]
    Local $stack[0]
    Local $token, $operator_a, $operator_b

    For $token = 0 To UBound($input) - 1
        Switch $input[$token]
            Case "("
                push($input[$token], $stack)

            Case ")"
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching ""("".")
                WEnd
                POP($stack)

            Case ","
                If peek($queue) = "(" Then msg("Misplaced "","" or ""("" !") ; *NEW*
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching ""("".")
                WEnd

            Case "+","-","*","/","^"
                $operator_a = $input[$token]
                While isoperator(peek($stack))
                    $operator_b = peek($stack)
                    if (associativity($operator_b) = "LEFT" and precedence($operator_a) = precedence($operator_b)) or (precedence($operator_a) < precedence($operator_b)) then
                        push(pop($stack), $queue)
                    Else
                        ExitLoop
                    EndIf
                WEnd
                push($operator_a, $stack)

            Case "function"
                push("function", $stack)

            Case Else
                push($input[$token], $queue)

        EndSwitch
    Next

    for $itemcount = 0 to ubound($stack) - 1
        if peek($stack) = "(" then msg("can't find a matching "")"".")
        push(pop($stack), $queue)
    next

    Return $queue

ENDFUNC
Edited by TheAutomator
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...