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

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 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
Share on other sites

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

Monkey's are, like, natures humans.

Share on other sites

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

Nice, thanks

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

Create an account

Register a new account

• Similar Content

• PixelGetColor() returns wrong color on Win11

By jiaojiaodubai,

• 10 replies
• 2,210 views

By BillDennis,

• 596 views
• Functions Speed Comparator

By Colduction,

• 0 replies
• 1,517 views
• Choose between Functions within GUI

By Emmhor1,

• 13 replies
• 5,309 views
• Array and functions

By AndreasNWWWWW,

• 3 replies
• 1,543 views
×

• Wiki
• AutoIt Resources

• FAQ
×
• Create New...