Задача 16.
Вводится скобочное арифметическое выражение. В выражении могут встречаться открывающая и закрывающая круглые скобки (и), знаки операций +, -, *, / (деление - целочисленное) и цифры от 0 до 9. Найти значение этого скобочного выражения.
Пример: '(3+5*2)/3-1'=3.
|
Решение задачи 16.
Для упрощения вычислений рассмотрите преобразование выражения в обратную польскую запись, т.е. в такую бесскобочную форму, в которой операнды записываются в том же порядке, что и в исходном выражении, а каждый знак операции следует непосредственно за операндами, над которыми эта операция проводится.
Пример: Выражение '(3+5*2)/3-1' преобразуется в '3 5 2 * + 3 / 1 -' (сначала будет выполняться операция * над предыдущими двумя операндами 5 и 2, результат 10 помещается на место чисел 5 и 2. Затем - операция + над предыдущими двумя операндами 3 и 10, результат 13 помещается на место 3 и 10, и т.д. Выражение в ходе вычисления будет принимать вид:
3 5 2 * + 3 / 1 -
3 10 + 3 / 1 -
13 3 / 1 -
4 1 -
3.
Алгоритм вычисления скобочного арифметического выражения. Преобразуем сначала выражение в обратную польскую запись. Каждой операции и открывающей скобке припишем приоритет:
Приоритет
(
0
+,-
1
*,/
2
Пустой стек
0
Шаг 1. Если во входной строке нет литер, то перейти к шагу 6; иначе прочитать следующий элемент (скобку, операцию или операнд) и обозначить его через x.
Шаг 2. Если x - операнд, то перенести его в выходную строку, поместить вслед за ним разделитель и вернуться у шагу 1.
Шаг 3. Если x - открывающая скобка, то поместить ее в стек и вернуться к шагу 1. Если x - закрывающая скобка, то перейти к шагу 4; иначе перейти к шагу 5.
Шаг 4. Если элемент, находящийся на вершине стека, не является открывающей скобкой, то перенести его из стека в выходную строку, поместить за ним разделитель, а затем повторить шаг 4. Если на вершине стека находится открывающая скобка, удалить ее из стека и вернуться к шагу 1.
Шаг 5. Если приоритет элемента на вершине стека не меньше приоритета x, то перенести этот элемент из стека в выходную строку, поместить за ним разделитель, а затем повторить шаг 5. Иначе поместить x на вершину стека и вернуться к шагу 1.
Шаг 6. Освободить стек, удаляя каждый раз по одному элементу и помещая его в выходную строку с последующим разделителем. Закончить работу.
Пример:
Этот алгоритм переводит выражение '(3+5*2)/3-1' в
'3 5 2 * + 3 / 1 -'.
Если в ходе построения обратной польской записи не переносить знак операции в выходную строку (где он бы стоял непосредственно за теми операндами, над которыми должна выполняться эта операция), а взять из выходной строки два последних операнда, выполнить над ними операцию, и результат поместить снова в выходную строку, то у нас после шага 6 в выходной строке окажется искомый результат.
Рассмотрим вычисления на примере выражения (3+5*2)/3-1
Очередной элемент входной строки
После обработки элемента
стек
выходная строка
(
(
Пустая
3
(
3
+
( +
3
5
( +
3 5
*
( + *
3 5
2
( + *
3 5 2
)
Пуст
Вместо переноса знака * в выходную строку, мы выполняем умножение над двумя
последними элементами выходной строки, при этом 5 и 2 из нее извлекаются, а результат умножения 10 - помещается в выходную строку. Она принимает вид: 3 10.
Далее мы должны были бы перенести знак + из стека в выходную строку, но вместо этого опять же выполняем сложение над двумя последними элементами и результат помещаем в выходную строку, так что она становится следующей:
13
/
/
13
3
/
13 3
-
-
Выполняем деление 13 на 3 Результат в выходную строку
4
1
-
4 1
входная строка пустая
пуст
В выходную строку помещаем результат 4-1=3. Это и есть значение выражения
Естественно в место выходной строки использовать стек чисел. Операции проводятся над двумя верхними элементами стека. Результат снова помещается в стек.
|
