маневровый двор алгоритм с функциями

Question

мой первый пост здесь :)

Я видел, что есть много вопросов по поводу алгоритма сортировочной станции, но я надеюсь, что еще есть участники форума, которые заинтересованы, чтобы помочь мне с еще одним вопросом об этом алгоритме.

Я сделал поиск через другие сообщения, чтобы увидеть, если мой ответ уже ответил, и я сделал некоторые исследования на других форумах и в Интернете на:

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, как языки ..

мой вопрос:

на данный момент алгоритм позволяет неправильное использование «(» и «)» пример: функции ((10 , 20,) 30) разрешено, но это явно не правильный способ вызвать функцию.

также я не уверен, что мой код написан правильно, псевдокод из Википедии был моей ссылкой, но ее не очень ясно :(

я также планирую расширить его, если это-то еще заявления и вложенными циклами и прочее, потому что главная цель состоит в том, чтобы написать какое-то интерпретатор в 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 

Answer 1

Вы может обрабатывать «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 из стека и добавьте токен функции к выходу.

«, »будет рассматриваться в аналогичном путь к ")", вызывающий появление операторов с более высоким приоритетом, но это не приведет к выходу функции оценки. Вам потребуется какой-то способ записать, сколько аргументов имеет функция.

В моем коде я использую рекурсия алгоритм. Алгоритм синтаксического анализа можно вызывать рекурсивно и ему предоставляется стоп-маркер. Когда встречается стоп-маркер, он возвращается из рекурсии. Когда функция встречается, она вызывает рекурсию, ожидающую «,» или «)».

---

Мне удалось запустить iut с помощью командной строки cscript. Я также добавил код отладки с Wscript.Echo.

Глядя на TOKEN_STACK, вы никогда не добавляли токен FUNCTION в стек, поэтому его не было, когда вы его искали.

Добавление СЛУЧАЙ "FUNCTION" ВЫЗОВ 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