Tom*_*Tom 6 vbscript interpreter function shunting-yard
我在这里发表的第一篇文章:)
我看到有很多关于调车场算法的问题，但我希望仍然有论坛成员有兴趣帮助我解决关于该算法的另一个问题。
我确实搜索了其他帖子，看看我的答案是否已经得到解答，并且我在其他论坛和互联网上做了一些研究：
http://stackoverflow.com/questions/16877546/modifying-the-shunting-yard-algorithm-c
http://www.computerhope.com/forum/index.php?topic=146535.0
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://www.autoitscript.com/forum/topic/164627-shunting-yard-with-functions/
我的代码是用 vb 脚本编写的，因为我喜欢它的简单性，而且我不了解 java 或 c 之类的语言。
我的问题：
目前该算法允许错误使用“(”和“)”示例：允许使用function((10,20,)30)，但这显然不是调用函数的正确方法。
我也不确定我的代码是否正确编写，来自维基百科的伪代码是我的参考，但它不是很清楚:(
我还计划用 if-else 语句和嵌套循环之类的东西来扩展它，因为主要目标是用类似 VB 的语言编写某种解释器作为学习项目:)
我的代码[编辑]：
SET PRECEDENCE = CREATEOBJECT("SCRIPTING.DICTIONARY")
WITH PRECEDENCE
.ADD "^",3
.ADD "*",2
.ADD "/",2
.ADD "%",2
.ADD "+",1
.ADD "-",1
.ADD "FUNCTION",0
.ADD "(",0
.ADD ",",0
.ADD ")",0
END WITH
'#############################################################################
tokenArray = split("FUNCTION ( ( A , B ) , C )")
msgbox SHUNTINGYARD(tokenArray)
'#############################################################################
FUNCTION SHUNTINGYARD(INPUT)
TOKEN_QUEUE = ARRAY()
TOKEN_STACK = ARRAY()
FOR TOKEN_NUMBER = 0 TO UBOUND(INPUT)
SELECT CASE INPUT(TOKEN_NUMBER)
CASE "("
CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_STACK)
CASE ")"
DO WHILE NOT( PRECEDENCE( PEEK(TOKEN_STACK) ) = 0 )
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
IF STACKISEMPTY(TOKEN_STACK) THEN CALL ERRORS("Can't find a matching ""("".", TRUE)
LOOP
IF PEEK(TOKEN_STACK) = "FUNCTION" THEN
DISCARD = POP(TOKEN_STACK)
CALL PUSH("@", TOKEN_QUEUE)
ELSE
DISCARD = POP(TOKEN_STACK)
END IF
CASE ","
DO WHILE NOT( PRECEDENCE( PEEK(TOKEN_STACK) ) = 0 )
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
IF STACKISEMPTY(TOKEN_STACK) THEN CALL ERRORS("Can't find a matching function ""("".", TRUE)
LOOP
CASE "+","-","*","/","^","%"
TOKEN_A = INPUT(TOKEN_NUMBER)
DO WHILE ISOPERATOR(PEEK(TOKEN_STACK))
TOKEN_B = PEEK(TOKEN_STACK)
IF (ASSOCIATIVITY(TOKEN_B) = "left" AND PRECEDENCE(TOKEN_A) = PRECEDENCE(TOKEN_B)) OR (PRECEDENCE(TOKEN_A) < PRECEDENCE(TOKEN_B)) THEN
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
ELSE
EXIT DO
END IF
LOOP
CALL PUSH(TOKEN_A, TOKEN_STACK)
CASE ELSE
CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_QUEUE)
END SELECT
NEXT
FOR ITEMCOUNT = 0 TO UBOUND(TOKEN_STACK)
IF PEEK(TOKEN_STACK) = "(" THEN CALL ERRORS("Can't find a matching "")"".", TRUE)'(
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
NEXT
SHUNTINGYARD = JOIN(TOKEN_QUEUE,"|")
END FUNCTION
'#############################################################################
FUNCTION ASSOCIATIVITY(ASSOC)
SELECT CASE LCASE(ASSOC)
CASE "^","\"
ASSOCIATIVITY = "right"
CASE ELSE
ASSOCIATIVITY = "left"
END SELECT
END FUNCTION
FUNCTION ISOPERATOR(ITEM)
ISOPERATOR = LEN(ITEM) = 1 AND INSTR("+-*/%^",ITEM)
END FUNCTION
SUB PUSH(ITEM,BYREF STACK)
IF UBOUND(STACK) > -1 THEN
REDIM PRESERVE STACK(UBOUND(STACK) + 1)
STACK(UBOUND(STACK)) = ITEM
ELSE
STACK = ARRAY(ITEM)
END IF
END SUB
FUNCTION POP(BYREF STACK)
IF UBOUND(STACK) > -1 THEN
POP = STACK(UBOUND(STACK))
REDIM PRESERVE STACK(UBOUND(STACK) - 1)
END IF
END FUNCTION
FUNCTION STACKISEMPTY(STACK)
IF UBOUND(STACK) > -1 THEN
STACKISEMPTY = FALSE
ELSE
STACKISEMPTY = TRUE
END IF
END FUNCTION
FUNCTION PEEK(STACK)
IF UBOUND(STACK) > -1 THEN
PEEK = STACK(UBOUND(STACK))
END IF
END FUNCTION
您可以像其他运算符一样对待“FUN”、“(”、“)”、“,”，并且可以将其推送到 TOKEN_STACK 上。（为了简洁起见，我将 FUNCTION 缩写为 FUN）。“FUN”、“(”、“)”、“,”的优先级低于“+”，因此优先级表看起来像
^ 4
* / % 3
+ - 2
( ) , FUN 1
考虑解析 1+FUN(2*3) 时会发生什么
Remaining Input Stack Output
1+FUN(2*3)
+FUN(2*3) 1
FUN(2*3) + 1
(2*3) + FUN 1
2*3) + FUN ( 1
*3) + FUN ( 1 2
3) + FUN ( * 1 2
) + FUN ( * 1 2 3
+ FUN ( * ) 1 2 3 Note 1
+ FUN ( ) 1 2 3 * Note 2
+ 1 2 3 * FUN()
1 2 3 * FUN() +
输出标记“FUN()”代表函数求值。
注1：当我们尝试将“）”压入堆栈时，所有具有更高优先级的运算符都会从堆栈中取出并移至输出。
注2：当栈尾的项是匹配的“(”时，则将其从栈中删除。有两种情况需要处理，简单匹配括号如1+(2*3)或如果有是堆栈上“(”之前的函数标记。在这种情况下，从堆栈中弹出 FUN 并向输出添加函数求值标记。
“,”的处理方式与“)”类似，导致优先级较高的运算符被弹出。但它不会导致函数评估被输出。您需要某种方法来记录函数有多少个参数。
在我的代码中，我使用基于递归的算法。解析算法可以递归调用，并给出一个停止令牌。当遇到停止标记时，它退出递归。当遇到一个函数时，它会调用递归等待“,”或“)”。
我设法使用 cscript 命令行程序让 iut 运行。我还使用 Wscript.Echo 添加了一些调试代码。
查看 TOKEN_STACK，您从未将 FUNCTION Token 添加到堆栈中，因此当您搜索它时它不在那里。
添加 CASE "FUNCTION" CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_STACK)
似乎给出了正确的东西。虽然我不确定当你匹配第一个右括号时会发生什么。像“E + FUNCTION (( A , B ) , C ) + F”这样的输入也会出现严重错误。
SET PRECEDENCE = CREATEOBJECT("SCRIPTING.DICTIONARY")
WITH PRECEDENCE
.ADD "^",3
.ADD "*",2
.ADD "/",2
.ADD "%",2
.ADD "+",1
.ADD "-",1
.ADD "FUNCTION",0
.ADD "(",0
.ADD ",",0
.ADD ")",0
END WITH
Wscript.Echo "Start"
'#############################################################################
tokenArray = split("FUNCTION ( ( A , B ) , C )")
'#tokenArray = split("A + B * C")
Wscript.Echo "Result " + SHUNTINGYARD(tokenArray)
'#############################################################################
FUNCTION SHUNTINGYARD(INPUT)
TOKEN_QUEUE = ARRAY()
TOKEN_STACK = ARRAY()
FOR TOKEN_NUMBER = 0 TO UBOUND(INPUT)
Wscript.Echo "Token " + INPUT(TOKEN_NUMBER)
Wscript.Echo "Stack " + JOIN(TOKEN_STACK,"|")
SELECT CASE INPUT(TOKEN_NUMBER)
CASE "("
CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_STACK)
CASE ")"
DO WHILE NOT( PRECEDENCE( PEEK(TOKEN_STACK) ) = 0 )
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
IF STACKISEMPTY(TOKEN_STACK) THEN CALL ERRORS("Can't find a matching ""("".", TRUE)
LOOP
IF PEEK(TOKEN_STACK) = "FUNCTION" THEN
DISCARD = POP(TOKEN_STACK)
CALL PUSH("@", TOKEN_QUEUE)
ELSE
DISCARD = POP(TOKEN_STACK)
END IF
CASE ","
DO WHILE NOT( PRECEDENCE( PEEK(TOKEN_STACK) ) = 0 )
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
IF STACKISEMPTY(TOKEN_STACK) THEN CALL ERRORS("Can't find a matching function ""("".", TRUE)
LOOP
CASE "+","-","*","/","^","%"
TOKEN_A = INPUT(TOKEN_NUMBER)
DO WHILE ISOPERATOR(PEEK(TOKEN_STACK))
TOKEN_B = PEEK(TOKEN_STACK)
IF (ASSOCIATIVITY(TOKEN_B) = "left" AND PRECEDENCE(TOKEN_A) = PRECEDENCE(TOKEN_B)) OR (PRECEDENCE(TOKEN_A) < PRECEDENCE(TOKEN_B)) THEN
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
ELSE
EXIT DO
END IF
LOOP
CALL PUSH(TOKEN_A, TOKEN_STACK)
CASE "FUNCTION"
CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_STACK)
CASE ELSE
CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_QUEUE)
END SELECT
NEXT
FOR ITEMCOUNT = 0 TO UBOUND(TOKEN_STACK)
IF PEEK(TOKEN_STACK) = "(" THEN CALL ERRORS("Can't find a matching "")"".", TRUE)'(
CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
NEXT
SHUNTINGYARD = JOIN(TOKEN_QUEUE,"|")
END FUNCTION
'#############################################################################
FUNCTION ASSOCIATIVITY(ASSOC)
SELECT CASE LCASE(ASSOC)
CASE "^","\"
ASSOCIATIVITY = "right"
CASE ELSE
ASSOCIATIVITY = "left"
END SELECT
END FUNCTION
FUNCTION ISOPERATOR(ITEM)
ISOPERATOR = LEN(ITEM) = 1 AND INSTR("+-*/%^",ITEM)
END FUNCTION
SUB PUSH(ITEM,BYREF STACK)
IF UBOUND(STACK) > -1 THEN
REDIM PRESERVE STACK(UBOUND(STACK) + 1)
STACK(UBOUND(STACK)) = ITEM
ELSE
STACK = ARRAY(ITEM)
END IF
END SUB
FUNCTION POP(BYREF STACK)
IF UBOUND(STACK) > -1 THEN
POP = STACK(UBOUND(STACK))
REDIM PRESERVE STACK(UBOUND(STACK) - 1)
END IF
END FUNCTION
FUNCTION STACKISEMPTY(STACK)
IF UBOUND(STACK) > -1 THEN
STACKISEMPTY = FALSE
ELSE
STACKISEMPTY = TRUE
END IF
END FUNCTION
FUNCTION PEEK(STACK)
IF UBOUND(STACK) > -1 THEN
PEEK = STACK(UBOUND(STACK))
END IF
END FUNCTION