Вопросы по алгоритму Shunting-yard

Question

Я реализовал синтаксический анализатор выражений в C++ после Shunting-yard algorithm, но у вас возникли проблемы с объяснением в википедии. Это в 'Алгоритм подробно' части:

If the token is an operator, o1, then: 

    while there is an operator token o2, at the top of the operator stack and either 

     o1 is left-associative and its precedence is less than or equal to that of o2, or 
     o1 is right associative, and has precedence less than that of o2, 

      pop o2 off the operator stack, onto the output queue; 

    at the end of iteration push o1 onto the operator stack. 

Он говорит "while there is an operator token o2", на мой undetstanding является "while there is an operator or function token o2".

Функции должны рассматриваться как операторы и иметь более высокий приоритет, чем все традиционные операторы, так ли это?

Answer 1

Я понимаю, что не должно быть путаницы между токенами operator и токенами function. В хорошо сформированном expression аргументы каждой функции должны быть заключены между левой и правой скобками. Хотя скобки в другом месте используются для наложения приоритета или просто для ясности. Основываясь на этом наблюдении, ответ на ваш вопрос

функцию следует рассматривать как оператор и имеет более высокий приоритет, чем все традиционные операторы, это правильно?

находится под номером

Когда говорят operator в описании алгоритма, то это означает operator и когда он говорит, это означает functionfunction. Для хорошо сформированного expression только чтение правильной круглой скобки приведет к появлению function, который в правой скобке закрывает список аргументов. Любая путаница между function и operator будет вводить в заблуждение вашу реализацию, чтобы дать интерпретацию неправильным выражениям. Представьте себе следующее выражение

4 + (sin 3 + 1) 

Если вы относитесь к function как оператор, вы будете давать смысл, что в то время как скобка могла бы быть просто неуместны.Вы также придадите смысл этому

4 - sin() 5*6 

Это становится более тонким, если вы рассматриваете функции с несколькими аргументами.

Answer 2

В нем говорится, что «хотя есть токен оператора o2», по моему непониманию есть «пока есть токен оператора или функции o2».

Функции должны рассматриваться как операторы и иметь более высокий приоритет, чем все традиционные операторы, так ли это?

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

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

В некоторых случаях вы можете уйти с ним, как sin a + b согласно приведенному выше алгоритму будет выходной a b + sin, который является таким же, как на выходе sin(a+b): в обоих случаях (с sin на вершине стека, или с ( на вершина стека), вы не вводите это в цикл выше, а нажмите + на стек.