Как проанализировать алгебраическое выражение

Question

Я собираюсь создать программу, которая может анализировать алгебраическое выражение.
Например:
<?php echo cal ('5*5+2*2'); ?>
Моя программа будет знать, что она умножит 5 на 5 и 2 сначала на 2, а затем на плюс. Я хочу проанализировать это сам, а не по php.

Answer 1

Я собирался предложить вам взглянуть на парсеры рекурсивного спуска , но, видимо, все пошло дальше, так как я делал это в середине 1980-х годов.Похоже, что грамматика выражения синтаксического анализа - это то, что вам нужно, если вы хотите понять теорию, лежащую в основе всего этого.

Если вас не волнует теория, то все в порядке:реализация теории означает, что вы все равно будете писать парсер рекурсивного спуска, так что вы можете просто сделать это: -)

Answer 2

Вы можете взять выражение 'infix' и, используя стек, превратить его в выражение 'prefix' или 'postfix', чтобы определить порядок операций (скобки, экспонирование, умножение или деление, сложение или вычитание).

Например, выражение ([5] [*] [5] [+] [2] [*] [2]) будет преобразовано в постфиксное выражение [5] [5] [*] [2] [ 2] [*] [+]. это выражение «postfix» теперь может читаться как «умноженное на пять и пять, умноженное на два и два, а затем сложенное вместе», что сохранит порядок операции.

Еще один способ представить идею «префикса / постфикса» - это использование нескольких стеков. Когда вы встретите число 5, поместите его в основной стек. Когда вы встретите символ умножения, сохраните его во вторичном стеке. Когда вы доберетесь до следующих 5, поместите его в основной стек, затем вытолкните все предметы из вашего второго стека и поместите их в свой основной стек.

После того, как вы определили операторы и операнды в правильном порядке, нужно выкинуть элементы из стека и затем оценить их.

Я помню, как решал эту проблему на моем курсе по информатике 102 в колледже. Вы делаете это для развлечения или просто пытаетесь понять это?