Формы представления алгебраических выражений
Рассмотрим в мкачестве примера использование стека для преобразования и вычисления алгебраических выражений.
Постфиксная запись представляет собой такую запись алгебраического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +. Здесь операндами операции * будут b и c (два ближайших операнда), а операндами операции + будут а и составной операнд b c *. Эта запись удобна тем, что она не требует скобок. Например, для выражения (a + b) * c постфиксная запись будет a b + c *. В этой записи не требуется ставить скобки для того, чтобы изменить порядок вычисления, зависящий от приоритета операций, как в исходном выражении. Поэтому постфиксная запись удобна для вычисления алгебраических выражений и широко применяется на практике.
В префиксной записи сначала наоборот записывается знак операции, а затем операнды. Например, для выражения a + b * c префиксная запись будет + a * b c. Префиксная запись также не требует расстановки скобок. Префиксную форму называют еще польской записью, а постфиксную – обратной польской записью.
Алгоритм Дейкстры перевода в постфиксную запись обрабатывает исходный массив лексем и строит новый массив из тех же лексем, расположенных в другом порядке. Кроме того, необходим еще стек – аналогичный массив, используемый для временного хранения операций.
Операции имеют разные приоритеты. Наименьший приоритет у операций ‘+’ и ‘-‘. Более высокий приоритет имеют операции ‘*’ и ‘/’. Еще более высокий приоритет у операции возведения в степень ‘^’. Самый высокий приоритет имеют операции операции, задаваемые функциями, такими как ‘sin‘, ‘cos’, ‘exp’. Заметим, что для этих операций требуется единственный операнд. Если операнд представляет собой выражение с другими знаками операций, то он должен заключаться в скобки.
|
|
|
Алгоритм первода выражения в постфиксную форму следующий:
- Константы и переменные кладутся в формируемую запись в порядке их появления в исходном массиве.
- При появлении операции в исходном массиве:
1) если в стеке нет операций или верхним элементом стека является открывающая скобка, операции кладётся в стек;
2) если новая операции имеет больший приоритет, чем верхняя операции в стеке, то новая операции кладётся в стек;
3) если новая операция левоассоциативная то есть вычисляется слева направо (‘+’, ‘-‘, ‘*’, ‘/’), то операции из стека большего или равного приоритета до ближайшей открывающей скобки или до конца стека перекладываются в формируемую запись, а новая операция кладётся в стек;
4) если новая операция правоассоциативная, то есть вычисляется справа налево (‘^’, ‘sin‘, ‘cos’, ‘exp’), то операции из стека большего приоритета до ближайшей открывающей скобки или до конца стека перекладываются в формируемую запись, а новая операция кладётся в стек.
|
|
|
- Открывающая скобка кладётся в стек.
- Закрывающая скобка выталкивает из стека в формируемую запись все операции до ближайшей открывающей скобки, открывающая скобка удаляется из стека.
- После того, как мы добрались до конца исходного выражения, операции, оставшиеся в стеке, перекладываются в формируемое выражение.
Примеры:
- a - b + c
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| a | a | 1 | |
| - | a | - | 2-1) |
| b | a b | - | 1 |
| + | a b - | + | 2-3) |
| c | a b - c | + | 1 |
| Конец | a b - c + | 5 |
После выталкивания операции из стека в результат при завершении работы порядок операций сменяется на противоположный.
- a + b - c * d
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| a | a | 1 | |
| + | a | + | 2-1) |
| b | a b | + | 1 |
| - | a b + | - | 2-3) |
| c | a b + c | - | 1 |
| * | a b + c | - * | 2-2) |
| d | a b + c d | - * | 1 |
| Конец | a b + c d * - | 5 |
- a + b * c - d
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| a | a | 1 | |
| + | a | + | 2-1) |
| b | a b | + | 1 |
| * | a b | + * | 2-2) |
| c | a b c | + * | 1 |
| - | a b c * + | - | 2-3) |
| d | a b c * + d | - | 1 |
| Конец | a b c * + d - | 5 |
|
|
|
- (a + b) * c
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| ( | ( | 3 | |
| a | a | ( | 1 |
| + | a | ( + | 2-1) |
| b | a b | ( + | 1 |
| ) | a b + | 4 | |
| * | a b + | * | 2-1) |
| c | a b + c | * | 1 |
| Конец | a b + c * | 5 |
- (a + b * c) / 2
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| ( | ( | 3 | |
| a | a | ( | 1 |
| + | a | ( + | 2-1) |
| b | a b | ( + | 1 |
| * | a b | ( + * | 2-2) |
| c | a b c | ( + * | 1 |
| ) | a b c * + | 4 | |
| / | a b c * + | / | 2-1) |
| 2 | a b c * + 2 | / | 1 |
| Конец | a b c * + 2 / | 5 |
- (a * (b + c) + d) / 2
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| ( | ( | 3 | |
| a | a | ( | 1 |
| * | a | ( * | 2-1) |
| ( | a | ( * ( | 3 |
| b | a b | ( * ( | 1 |
| + | a b | ( * ( + | 2-1) |
| c | a b c | ( * ( + | 1 |
| ) | a b c + | ( * | 4 |
| + | a b c + * | ( + | 2-3) |
| d | a b c + * d | ( + | 1 |
| ) | a b c + * d + | 4 | |
| / | a b c + * d + | / | 2-1) |
| 2 | a b c + * d + 2 | / | 1 |
| Конец | a b c + * d + 2 / | 5 |
- a ^ b ^ c
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| a | a | 1 | |
| ^ | a | ^ | 2-1) |
| b | a b | ^ | 1 |
| ^ | a b | ^ ^ | 2-4) |
| c | a b c | ^ ^ | 1 |
| Конец | a b c ^ ^ | 5 |
|
|
|
- sin cos a
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| sin | sin | 1 | |
| cos | sin cos | 3-4) | |
| a | a | sin cos | 1 |
| Конец | a cos sin | 5 |
- exp ( a * ln b)
| Обрабатываемая лексема | Результат | Стек | Пункт алгоритма |
| exp | exp | 1 | |
| ( | exp ( | 3 | |
| a | a | exp ( | 1 |
| * | a | exp ( * | 2-2) |
| ln | a | exp ( * ln | 2-2) |
| b | a b | exp ( * ln | 1 |
| ) | a b ln * | exp | 4 |
| Конец | a b ln * exp | 5 |
Вычислить значение выражения, записанного в постфиксной записи, очень просто. Просматриваем постфиксную запись. Значения переменных и констант кладутся в стек. Когда встречается операция, из стека берутся два верхних значения, вычисляется результат применения операции к этим значениям, и результат помещается в стек. Если встречается функция, то берётся одно значение из стека, а результат помещается в стек на его место.
Примеры:
- Вычислим значение выражения a b c + * d + 2 / при а = 1, b = 2, c = 3, d = 4
| Обрабатываемая лексема | Стек |
| a | 1 |
| b | 1 2 |
| c | 1 2 3 |
| + | 1 5 |
| * | 5 |
| d | 5 4 |
| + | 9 |
| 2 | 9 2 |
| / | 4.5 |
- Вычислим значение выражения x x sin 2 * + при x = 3.14
| Обрабатываемая лексема | Стек |
| x | 3.14 |
| x | 3.14 3.14 |
| sin | 3.14 0 |
| 2 | 3.14 0 2 |
| * | 3.14 0 |
| + | 3.14 |
Очереди и их применение
Вторым распространенным типом линейных списков являются очереди. Это список типа FIFO (первым пришел – первым вышел) с двумя точками входа: начало и конец. Очередь пополняется с конца и продвигается с начала.
В жизни все мы сталкиваемся с очередями (за билетами, на дежурство и т.п.). В программировании часто приходится иметь дело с очередями на получение различных системных ресурсов. Очереди используются для реализации поиска в ширину, что будет рассматриваться в будущем.
Аналогично стекам очереди могут быть организованы на основе массивов или динамических структур. При использовании массива начало очереди находится в первом элементе, а конец задается индексом и меняется при изменении очереди. Впрочем, возможно расположить очередь в массиве и в противоположном направлении.
Пусть очередь описана Var Och[1..N] of T, где T – тип элементов очереди. Конец очереди задан индексом Endo.
Постановка в очередь производится командами
Endo:= Endo+1;
Och[Endo]:=NewElement;
Продвижение очереди выполняется команками
For I:=1 to Endo-1 do Och[I]:= Och[I+1];
Endo:= Endo-1;
Как и для стека, необходимо проверять выход за границы массива при постановке и непустоту очереди при удалении элементов.
При организации очереди на основе указателей используется следующее описание
Type
Ukaz=^Och;
Och=record
Info: …;
{ поля информационной части элемента }
Next: ukaz
end;
Var
Bego, Endo: ukaz; { начало и конец очереди }
Выгодно указатели Next ориентировать в направлении от начала очереди к концу, а не наоборот. В этом случае постановка в очередь выполняется командами
New(Kon);
Endo^.Next:=Kon;
Kon^.Next:=Nil;
и далее присвоение значений информационным полям.
Дата добавления: 2018-11-24; просмотров: 1325; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!