Sign in to follow this  
Followers 0
TheAutomator

Shunting Yard With Functions?

7 posts in this topic

#1 ·  Posted (edited)

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



Now you can consult my signature.


_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_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: 04/09/2015

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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

#5 ·  Posted (edited)

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

#6 ·  Posted (edited)

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

#7 ·  Posted (edited)

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  
Followers 0

  • Similar Content

    • 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?
    • IamKJ
      By IamKJ
      I am trying to allow the GUI to gather info as to when to execute a function.  I am having trouble doing this.  So far this is what I have.
       
      ;Timer Func timer () If Not IsDeclared("iMsgBoxAnswer") Then Local $iMsgBoxAnswer $iMsgBoxAnswer = MsgBox(36,"Timer","Please format your answer in 00:00:00:000") Select Case $iMsgBoxAnswer = 6 ;Yes Global $infotime = InputBox ('Time', 'What time to execute?') Do $rawtimer = ToolTip(@Hour & ':' & @Min & ':' & @Sec & ':' & _MSec()) until $rawtimer = $infotime if $rawtimer = $infotime Then msgbox (0,'Worked','Worked') Else EndIf Case $iMsgBoxAnswer = 7 ;No Exit EndSelect EndFunc Func _MSec() Local $stSystemTime = DllStructCreate('ushort;ushort;ushort;ushort;ushort;ushort;ushort;ushort') DllCall('kernel32.dll', 'none', 'GetSystemTime', 'ptr', DllStructGetPtr($stSystemTime)) $sMilliSeconds = StringFormat('%03d', DllStructGetData($stSystemTime, 8)) $stSystemTime = 0 Return $sMilliSeconds EndFunc I have also tried _GUIToolTip_GetText in order to read the tooltip until the time specified, but it still doesn't work.  Any help would be great.
    • XOblivion
      By XOblivion
      im some what new to autoit and need help figuring out best way to make a simple clicker for few idle games i play(taptitdue, sakura clicker, elndless frontier etc.) ive played around with autoit recorder to make simple copy mouse clicks. but now i want to make a script that allows me to select multiple functions before starting the script for game ex: click section A or click section A + B to run At set intervals if that makes sense . i dont need scripts made by other just info on what things i should use to make it my self.
       
      need to be able to select between games and be able to select multiple functions to run inconjuntion or independent for each game. thank you in advance
    • BetaLeaf
      By BetaLeaf
      Hi guys. I am trying to make a soundboard app. 
      Here is the code I have so far
      #include "Misc.au3" #RequireAdmin;needed to work in some games. #include "array.au3" Opt("WinTitleMatchMode", -2) If @OSArch = "x64" Then Global $VLC_Path = "C:\Program Files (x86)\VideoLAN\VLC\vlc.exe" Global $VLC_WorkingDir = "C:\Program Files (x86)\VideoLAN\VLC\" Else Global $VLC_Path = "C:\Program Files\VideoLAN\VLC\vlc.exe" Global $VLC_WorkingDir = "C:\Program Files\VideoLAN\VLC\" EndIf Global $sectionData = IniReadSectionNames(@ScriptDir & "\SoundBoard.ini") If @error Then IniWriteSection(@ScriptDir & "\SoundBoard.ini", "Sound1", 'File="' & @UserProfileDir & '\Music\SampleTrack.mp3"' & @CRLF & 'StartTime="12"' & @CRLF & 'EndTime="34"' & @CRLF & 'PlaybackDevice="Microsoft Soundmapper"' & @CRLF & 'Hotkey="+{numpad9}"') MsgBox(16, "SoundBoard", "SoundBoard.ini is missing. It has been created for you.") ShellExecute(@ScriptDir & "\SoundBoard.ini", "", "", "edit") InputBox("SoundBoard", "Notes:" & @CRLF & "StartTime and EndTime are in seconds. Available Hotkeys can be found at the following url:", "https://www.autoitscript.com/autoit3/docs/functions/Send.htm") Exit EndIf For $i = 1 To $sectionData[0] Local $iArray = IniReadSection(@ScriptDir & "\SoundBoard.ini", $sectionData[$i]) For $j = 1 To UBound($iArray) - 1 Local $result = Assign("SoundBoard" & $i & "_" & $j, IniRead(@ScriptDir & "\SoundBoard.ini", $sectionData[$i], $iArray[$j][0], $iArray[$j][1]), 2) If $result = 1 Then Consolewrite("Variable Assigned: SoundBoard" & $i & "_" & $j & @CRLF & "Data=" & $iArray[$j][1]&@CRLF) Else Consolewrite("Variable was not assigned: SoundBoard" & $i & "_" & $j & @CRLF & "Data=" & $iArray[$j][1]&@CRLF) EndIf Next Next For $i = 1 To $sectionData[0] Local $Hotkey = Eval("SoundBoard"&$i&"_5") ConsoleWrite("Processing Hotkey "&$Hotkey&@CRLF) ;NEED HELP HERE ; HotKeySet($Hotkey,"") Next While 1 Sleep(500);idle to prevent unnecessary work. 10 is the minimal we can set this value to. WEnd Func LoadVLC($iPlayFile, $iPlayFileStartTime, $iPlayFileEndTime, $iPlayAudioDevice = "Microsoft Soundmapper") ShellExecuteWait($VLC_Path, '--qt-start-minimized --play-and-exit --start-time="' & $iPlayFileStartTime & '" --stop-time="' & $iPlayFileEndTime & '" --aout=waveout --waveout-audio-device="' & $iPlayAudioDevice & '" "' & $iPlayFile & '"', $VLC_WorkingDir, "", @SW_HIDE) Beep(500, 200) EndFunc ;==>LoadVLC For example, I have a song called "MoonlightSonata.mp3" and I want to activate it with hotkey !{numpad9}. However, hotkeyset does not allow sending of flags so I cannot use LoadVLC as it is now. I need to create a function that stores the flags using the data from the earlier Inireads. Ik how to use the data but not how to create the function to store that data. I looked at IsFunc() second example but I do not understand. Sorry if I am not being clear on what I am trying to do. My brain is fried right now after trying various things for an hour. Any help would be appreciated. 
      The idea is to be able to have a dedicated hotkey for each sound I want to play so I will need to have my script create a new function by itself using the data from the INI.
      hotkeyset("$hotkey1","MySoundBoard1") hotkeyset("$hotkey2","MySoundBoard2") func MySoundBoard1() LoadVLC("MoonlightSonata.mp3") ;the other flags are optional and will not be set for simplicity. endfunc func MySoundBoard1() LoadVLC("TheBananaSong.mp3") endfunc Honestly I don't care how it is done as long as I have a dedicated hotkey for each entry in my ini.  An example of such an entry looks like
      [Sound1] File="C:\Users\BetaL\Music\SampleTrack1.mp3" StartTime="12" EndTime="34" PlaybackDevice="Microsoft Soundmapper" Hotkey="!{numpad8}" [Sound2] File="C:\Users\BetaL\Music\SampleTrack2.mp3" StartTime="24" EndTime="43" PlaybackDevice="Microsoft Soundmapper" Hotkey="!{numpad9}" Am I making any sense? Please let me know.
       
      Edit: Huge thanks to @Melba23 for the learning experience, his time, and help.
    • dynamitemedia
      By dynamitemedia
      i have the following snippet...   now its working but i have it inside a function and want to be able to use   $aThumb[$i]  outside the function in the rest of the script, i tried return and keep getting this error  "Invalid keyword at the start of this line.:"  
      Global $iRows = UBound($a, $UBOUND_ROWS) Global $iCols = UBound($a, $UBOUND_COLUMNS) $oID = $oID + 1 $oURL = $oString.selectSingleNode("./url") $oName = $oString.selectSingleNode("./name") $oCategory = $oString.selectSingleNode("./category") $oThumb = $oString.selectSingleNode("./image") $oLanguage = $oString.selectSingleNode("./language") $aThumb = [$iRows] _ArrayAdd($aThumb, $oThumb.text) For $i = 1 To UBound($aThumb) - 1 ConsoleWrite($oID & @TAB & $aThumb[$i] & @CRLF) Next Next ConsoleWrite( "rows: " & $iRows & @CRLF) Thanks for your help