Jump to content
Sign in to follow this  
TheAutomator

Shunting Yard With Functions?

Recommended Posts

TheAutomator

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

Share this post


Link to post
Share on other sites
guinness

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

Share this post


Link to post
Share on other sites
TheAutomator

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

Share this post


Link to post
Share on other sites
TheAutomator

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

Share this post


Link to post
Share on other sites
TheAutomator

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

Share this post


Link to post
Share on other sites
TheAutomator

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

Share this post


Link to post
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
Sign in to follow this  

  • Similar Content

    • Emmhor1
      By Emmhor1
      Hi All,

      MAIN QUESTION:
      Is it possible to Call specific function within a GUI

      So I have a script with multiple functions although I don't want to use every function every time.
      My Idea is to create a simple GUI which allows me to select what functions I want to use then run the funtions by clicking a button.
      I have already made a GUI which allows me to select specific .exe's I would like to run after selection it runs the .exe one by one.
      This script is on my work laptops and cannot access it right now.
       
      Who can help me with this?
      GUIcreate
      Func1 
      Func2
      Func3
      Then have a boxes which allows me to select the specif Func.(I used GUIChecked and Unchecked in my other script)
      Then a button which executes/calls the selected functions
    • AndreasNWWWWW
      By AndreasNWWWWW
      I got a question:  i am trying to run different functions based upon what i select in these radio buttons.(code below)
      it needs to check server 1. then run function 1 or function 2 after what i selected in the checkbox.
      once that function is done it moves to the next one, until it has been trough all 5 
       
      iv'e tried using while loops with different while $i equals to something but then i manualy need to go in and edit the script every time.
      #include <ButtonConstants.au3> #include <GUIConstantsEx.au3> #include <StaticConstants.au3> #include <WindowsConstants.au3> #Region ### START Koda GUI section ### Form= $Form1 = GUICreate("Form1", 615, 437, 192, 124) $Server2 = GUICtrlCreateLabel("Server2", 216, 95, 41, 17) $server1 = GUICtrlCreateLabel("Server1", 216, 72, 41, 17) $server4 = GUICtrlCreateLabel("Server4", 216, 144, 41, 17) $server3 = GUICtrlCreateLabel("Server3", 216, 119, 41, 17) $server5 = GUICtrlCreateLabel("Server5", 216, 170, 41, 17) $Start = GUICtrlCreateButton("Start", 240, 248, 147, 25) $Checkbox1 = GUICtrlCreateCheckbox("function1", 288, 72, 97, 17) $Checkbox2 = GUICtrlCreateCheckbox("function2", 392, 72, 97, 17) $Checkbox3 = GUICtrlCreateCheckbox("function1", 288, 96, 97, 17) $Checkbox4 = GUICtrlCreateCheckbox("function2", 392, 96, 97, 17) $Checkbox5 = GUICtrlCreateCheckbox("function1", 288, 120, 97, 17) $Checkbox6 = GUICtrlCreateCheckbox("function2", 392, 120, 97, 17) $Checkbox7 = GUICtrlCreateCheckbox("function1", 288, 144, 97, 17) $Checkbox8 = GUICtrlCreateCheckbox("function2", 392, 144, 97, 17) $Checkbox9 = GUICtrlCreateCheckbox("function1", 288, 170, 97, 17) $Checkbox10 = GUICtrlCreateCheckbox("function2", 392, 170, 97, 17) GUISetState(@SW_SHOW) #EndRegion ### END Koda GUI section ### While 1 $nMsg = GUIGetMsg() Switch $nMsg Case $GUI_EVENT_CLOSE Exit EndSwitch WEnd  
    • wsc77320
      By wsc77320
      Maybe I am trying this all wrong, but hope someone can help. I have a GUI and want to click a button which will start a function to get a folder location. Then I need to pass that location to a variable to use outside the function. Here is a sample of the code;It prompts to choose a file location and the message box displays the choice but that is all inside the function. I need to pass the path selected outside the function. OR need a different way of doing this, maybe my approach is wrong.
      $Label_Drive=GUICtrlCreateLabel("Use the select button and choose where profiles will be stored.", 15, 120, 240, 25)
      $BTN_Set_BKP_Path = GUICtrlCreateButton("Select Location", 250, 120, 90, 30) ;left,top,width,heigth
      GUICtrlSetOnEvent($BTN_Set_BKP_Path, "Location")
       
      Func Location()
      $BKP_Path = FileSelectFolder("Select a folder where profiles will be stored.", "c:\")
      MsgBox(0,"Select Path", "You set the path as " & $BKP_Path)
      EndFunc
       
      $Label_BKP_Path=GUICtrlCreateLabel("Current path is " & $BKP_Path & ".", 15, 150, 300, 25)
       
       
    • Karnalsyn
      By Karnalsyn
      As with a lot of programming, the less manual repetition done to achieve the same outcome...the better.
      I package programs for network deployment at the organization I work for. Sometimes these applications require verbose messaging to the user, and sometimes by special request we have to turn that off and deploy silently.
      The way I currently handle these 2 scenarios is this.
      I have a function that builds the splashwin display screen to variable size depending on message length, and displays the desired message to the end user.
      Then at each point throughout my script as I need to make the user aware of what is currently happening, I inject a splashwin function call with the unique message pertaining to that specific event. ie. "Installing Microsoft Office, please wait..."
      In effort to build a more universal script to handle any type of request submitted. I've incorporated a switch command of '/silent'
      If cmdlineraw detects the usage of that switch when the script is triggered it sets a variable flag, ie. $silent = "on"
      Then at every splashwin call I make, I'm prefixing it with an IF statement that checks for the flag, and then does NOT display the message if that flag is "on". Or does display it if its not. Has worked for me just fine. But while I grow my programming skills and look for more streamlined ways of handling areas I find myself creating repetition. I'm curious if I can relocate that flag check. Taking it out of every single splashwin call, and injecting it into the function itself.
      Example of how I currently display or hide the splashwin based on command line...
      If StringInStr($cmdlineraw, "/silent", 0) Then
          $SilentSwitch = "ON"
      EndIf
      If $SilentSwitch = "OFF" Then SplashWin($Uninstalling & $ProductInfo[1][0])
      Some scripts have dozens of those splashwin calls littered throughout, so Is this the best approach I can take already? Or as stated earlier, can I pull the IF statement away from the splashwin call. And left the function as a whole either activate or deactivate as a result of the command line check.
    • cosmos
      By cosmos
      Edit: Just realised this was posted in the wrong forum! I guess the Mods will move it to either "AutoIt General Help and Support" or "AutoIt Technical Discussion".
      Do you use type checking? Or do you choose not to type check?
      I was trying to think of the simplest way to do a type check without typing arguments more than once and I came up with:
      Func displayPerson($firstName, $lastName, $age) ; -- TYPE CHECK -- Local $typeCheck = ("" _ & IsString($firstName) _ & IsString($lastName) _ & IsNumber($age) _ ) If (StringInStr($typeCheck, "0")) Then MsgBox(16, "Type Error: displayPerson()", $typeCheck) ; -- FUNCTION -- MsgBox(0, "", $firstName & " " & $lastName & " (" & $age & ")") EndFunc The only catch with this method is that it produces a very simplistic error message. Even still, the fact that you only have to type out arguments once makes it a reasonable approach, in my opinion. The same logic can also be used for making function contracts (for example: $firstName mustn't be an empty string etc...).
      What do you think? How do you go about such things?
×