2.4 Алгоритм синтаксического анализатора, разработанного на основе обратной польской записи

Рассмотрим систему нелинейных уравнений (2.4), заданную в текстовом формате.

x001+x001^2 -2*x002x003-0,1=0

x002-x002^2+sin(3*x001*x003)+0,2=0 (2.4)

x003+cos(x003^2)+2*x001*x002-0,3=0

Система (2.4) состоит из 3-х нелинейных уравнений и соответственно из 3-х неизвестных: x001, x002, x003. Представляя уравнения (2.4) как функции, можем записать (2.5).

f1(x001, x002, x003)=x001+x001^2 -2*x002x003-0,1

f2(x001, x002, x003)=x002-x002^2+sin(3*x001*x003)+0,2=0 (2.5)

f3(x001, x002, x003)=x003+cos(x003^2)+2*x001*x002-0,3=0

При нахождении промежуточных значений функций итерационного процесса решения системы, можно сделать следующие шаги:

− заменить в (2.4) все части x002x003 на x002*x003;

− все выражения, заключенные в скобки (x002+x003)(x066*x003) заменить на (x002+x003)*( x066*x003);

− заменить все тригонометрические функции на значения.

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

В математике существует древняя традиция помещать оператор между операндами (x+y), а не после операндов (xy+). Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича, который изучал свойства этой записи.

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

– любая формула может быть выражена без скобок;

– она удобна для вычисления формул в машинах со стеками;

– инфиксные операторы имеют приоритеты, которые произвольны и нежелательны.

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

а) если этот символ − число (или переменная), то просто помещаем его в выходную строку;

б) если символ − знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка. Получив один из этих символов, проверяем стек: 

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

2) если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие, затем переходим к пункту 1);

в) если текущий символ – это открывающая скобка, то помещаем ее в стек;

г) если текущий символ – это закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (то есть символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.

Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку. Далее необходимо вычислить выражение, записанное в обратной польской записи. Для реализации этого алгоритма используется стек для чисел (или для переменных, если они встречаются в исходном выражении). В качестве входной строки рассматривается выражение, записанное в ОПЗ:

а) если очередной символ входной строки – число, он помещается в стек;

б) если очередной символ – это знак операции, то извлекаем из стека два верхних числа, используем их в качестве операндов для этой операции, затем кладем результат обратно в стек.

Когда вся входная строка будет разобрана в стеке должно остаться одно число, которое и будет результатом данного выражения.