Арифметические выражения состоят из операндов и знаков операций, при этом под операндом следует понимать знак-цифровое выражение, обозначающее некую формальную переменную.
V = { [a-z], [0-9], +, -, *, /, **, ), ( }
Алгебраические выражения включают в себя все арифметические выражения, а также описания алгебраических функций.
Логическое выражение - это объединение алгебраических выражений и логических функций.
В арифметических выраженниях существует два типа операций.
Одноместные операции (операции с одним операндом) и двуместные операции (оперaции с двумя операндами).
-B + А * С
"-" - одноместная операция, "*" - двуместная.
Для получения алгебраических и арифметических выражений используются стековые методы трансляции. Для этого применяются
два стека и т.н. таблица переходов. Таблица переходов определяет старшинство выполняемых операций и связывает последовательность действий.
Используемые стеки:
- стек транслятора (внутреннее представление);
- стек для исполнения
Правила получения польской записи
1. Идентификаторы польской записи следуют в том же порядке, что и в инфиксной записи.
(a+b)/c
ab+c/ - постфиксная запись;
+ab/c - инфиксная запись.
2. Операторы в польской записи следуют в том же порядке, в каком они должны вычисляться при чтении выражения слева направо.
3. Операторы располагаются непосредственно за своими операндами.
<идентификатор>
<операнд>
<оператор>
<оператор> ::= <идетификатор> | <операнд>
<операнд><оператор>;
При стековой трансляции выражений выполняются два типа команд транслятора:
1. ki - взять операнд с именем i и отправить его на вершину стека, перейти к просмотру следующего символа;
2. kξ - взять два верхних операнда из стека, произвести над ними операцию ξ и новый операнд (результат) поместить на вершину стека
η - символ на вершине стека транслятора;
ξ - символ, который принимаетсчя транслятором.
При выполнении этих команд возможно четыре действия транслятора:
I - отправить пришедший символ на вершину стека и читать следующий символ;
II - выполнить операцию над двумя операндами, результат занести на вершину стека и читать следующий символ;
III - при прочтении символа ')' удалить ')' с вершины стека и читать следующий символ (действие удаления скобки);
IV - взять два операнда, выполить над ними команду kξ и повторить чтение входного символа.
На вершине стека не может быть символа ')'.
λ - пустой символ (пробел, пустота на вершине стека, заключающий символ).
Ош - ошибка
Пример:
(a * b + c * d) / (A - d) + b * c
Таблица 1
| T | ξ | действие | команда |
| λ | ( | I | - |
| ( | a | - | ka |
| ( | * | I | - |
| (* | b | - | kb |
| (* | + | IV | ka |
| ( | +(повтор) | I | - |
| (+ | c | - | kc |
| (+ | * | I | - |
| (+* | d | - | kd |
| (+* | ) | IV | k* |
| (+ | )(повтор) | IV | k+ |
| ( | )(повтор) | III | - |
| λ | / | I | - |
| / | ( | I | - |
| /( | A | - | kA |
| /( | - | I | - |
| /(- | d | - | kd |
| /(- | ) | IV | k- |
| /( | )(повтор) | III | - |
| / | + | IV | k/ |
| λ | +(повтор) | I | - |
| + | b | - | kb |
| + | * | I | - |
| +* | c | - | kc |
| +* | λ | IV | k* |
| + | λ(повтор) | IV | k+ |
| λ | λ(повтор) | k | - |
ab*cd*+Ad-/bc*+
Представление арифметических, алгебраических и логических выражений в виде тетрад.
Тетрады - представление выражений в виде:
1. для бинарных операций
<оператор><операнд1><операнд2><результат>
A * B
* A B T, где Т - результат
2. для унарных операций:
<оператор><операнд>< ><результат>
-B + C * D
-B _ T1
*C D T2
+ T1 T2 T3
В отличие от обычной инфиксной записи, тетрады раполагаются в том порядке, в котором они должны выполняться.
