Одно и тоже арифмитическое выражение может быть записанно тремя способами:
1. Инфиксный способ ((a/(b+c)+(x*(y-z))
2. Префексный способ +(/(a,+(b,c)),*(x,-(y,z)))
3. Постфиксный способ ((a,(b,c)+)/,(x,(y,z)-)*)+
Вид ДСА не зависит от способоа записи выражения, поскольку определяет его не форма записи, а порядок выполнения операции, но процесс построения дерерва конечно зависит от способа записис выражения. Разберем все три варианта алгоритма построения ДСА(дерево синтаксического анализа)
1) инфиксной записи. Для простоты будем считать что правильное арифмитическое выражение, задаеться в одной строке, без пробелов, каждый операнд записан одним символом. Приоретет операций задаеться скобками, ими должна быть снабжена каждая операция.
Алгоритм:
Если не достигнут конец строки ввода прочитать символ, если этот символ открываюшая скобка, то создать новую вершину дерева, вызвать алгоритм инфикс для левого поддерева. Прочитать символ операции и занести его в текушию вершину, вызвать алгоритм инфикс для правого поддерева. Прочитать символ закрывашей скобки и ничего с ним не делать. Иначе создать новую вершину дерева и занести в нее этот символ.
Procedure Infix(var p:Ptree);