Разбор выражения с функциями

Question

Это моя ситуация: входные данные представляют собой строку, содержащую обычную математическую операцию, например 5+3*4. Функции также возможны, то есть min(5,A*2). Эта строка уже разбита на токены, и теперь я хочу ее проанализировать с помощью стеков (поэтому нет AST). Сначала я использовал алгоритм Shunting Yard, но здесь возникает моя главная проблема:

Предположим, у вас есть эта (токенизированная) строка: min(1,2,3,+), что, очевидно, является неверным синтаксисом. Тем не менее, SYA превращает это в выходной стек 1 2 3 + min(, и, надеюсь, вы увидите, что проблема возникнет. При синтаксическом анализе слева направо он сначала видит +, вычисляя 2+3=5, а затем вычисляя min(1,5), что приводит к 1. Таким образом, мой алгоритм говорит, что это выражение вполне нормально, в то время как он должен вызвать синтаксическую ошибку (или что-то подобное).

Каков наилучший способ предотвратить подобные вещи? Добавить специальный разделитель (например, запятую), использовать другой алгоритм или что?

Answer 1

Чтобы предотвратить эту проблему, вам, возможно, придется отслеживать глубину стека. То, как я это сделал (и я не уверен, что это «лучший» способ), - это другой стек.

Новый стек соответствует следующим правилам:

• Когда открываются круглые скобки, ( или функция анализируется, нажмите 0.
  • Сделайте это в случае вложенных функций
• Когда закрывающие скобки, ), анализируются, извлеките последний элемент и добавьте его к новому последнему значению в стеке.
  • Число, которое только что появилось, - это количество значений, возвращенных функцией. Вы, вероятно, хотите, чтобы это всегда было 1.
• Когда анализируется запятая или подобный разделитель, выскочите из стека, добавьте это число к новому последнему элементу, а затем нажмите 0.
  • Сброс, чтобы мы могли начать проверку следующего аргумента функции
  • Значение, которое только что было получено, - это сколько значений было возвращено оператором. Вы, вероятно, хотите, чтобы это всегда было 1.
• Когда число помещается в output, увеличивается верхний элемент этого стека.
  • Это сколько значений доступно в output. Числа увеличивают количество значений. Бинарные операторы должны иметь как минимум 2.
• Когда бинарный оператор помещается в output, уменьшать верхний элемент
  • Бинарный оператор принимает 2 значения и выводит 1, тем самым сокращая общее количество значений, оставшихся на выходе, на 1.
  • Как правило, n -ный оператор, который принимает n значений и возвращает m значений, должен добавить ( mn ) к верхний элемент.
  • Если это значение станет отрицательным, выведите ошибку!

Это обнаружит, что последний аргумент в вашем примере, который просто содержит +, будет уменьшать вершину стека до -1, автоматически выдавая ошибку.

Но тогда вы можете заметить, что последний аргумент в вашем примере, скажем, 3+ вернет ноль, который не является отрицательным. В этом случае вы бы выдавали ошибку на одном из шагов, где «вы, вероятно, хотите, чтобы это всегда было 1».