5060. Обратная польская запись
Обратная
Польская Запись (ОПЗ) – это математическая запись выражения, в которой каждый
оператор следует за своими операндами. Она известна как постфиксная нотация и
не содержит в себе скобок, если каждый оператор имеет фиксированное количество
операндов.
Например:
·
выражение 2 + 4 в ОПЗ представляется как 2 4 +
·
выражение 2 * 4 + 8 в ОПЗ представляется как 2 4 * 8 +
·
выражение 2 * (4 + 8) в ОПЗ представляется как 2 4 8 +
*
Вычислите
арифметическое выражение, записанное в Обратной Польской Записи. Возможными
операторами являются +, -, *, /. Операцию деления считать целочисленной (14 / 3
= 4). Каждым операндом может быть либо число, либо другое арифметическое
выражение.
Вход. Одна
строка, которая содержит выражение в Обратной Польской Записи. Длина выражения
не более 100 символов.
Выход. Выведите
значение выражения, заданного в Обратной Польской Записи.
|
Пример входа 1 |
Пример выхода 1 |
|
2 4 * 8 + |
16 |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
2 4 8 + * |
24 |
РЕШЕНИЕ
стек
Анализ алгоритма
Разобьем
входное выражения на термы, которыми выступают число или один из четырех
операторов. Термы будем обрабатывать следующим образом:
·
если терм – число, то заносим его в стек;
·
если терм – оператор, то извлекаем из стека два числа,
произведем над ними указанную операцию и занесем результат в стек.
По
завершению обработки выражения стек содержит оно число – результат вычислений.
Пример
Выражение “2 4 * 8 +” эквивалентно “2
* 4 + 8”.
Выражение “2 4 8 + *” эквивалентно “2
* (4 + 8)”.
Реализация алгоритма
Объявим
рабочий массив и стек.
char s[200];
stack<int> st;
Читаем
термы до конца выражения, последовательно обрабатываем их.
while(scanf("%s",s)
== 1)
{
Обрабатываем
четыре арифметические операции.
if (s[0] == '+')
{
a = st.top();
st.pop();
b = st.top();
st.pop();
st.push(a+b);
} else
if (s[0] == '-')
{
a = st.top();
st.pop();
b = st.top();
st.pop();
st.push(b-a);
} else
if (s[0] == '*')
{
a = st.top();
st.pop();
b = st.top();
st.pop();
st.push(a*b);
} else
if (s[0] == '/')
{
a = st.top();
st.pop();
b = st.top();
st.pop();
st.push(b/a);
} else
Терм val является числом. Преобразуем его из строкового
представления в число и заносим в стек.
{
sscanf(s,"%d",&val);
st.push(val);
}
}
Выводим
результат выражения, который находится на вершине стека.
printf("%d\n",st.top());
Java реализация
import java.util.*;
public class Main
{
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
Stack<Integer> st = new
Stack<Integer>();
while(con.hasNext())
{
String s = con.next();
if (s.equals("+"))
{
Integer a = st.pop();
Integer b = st.pop();
st.push(a + b);
} else
if (s.equals("-"))
{
Integer a = st.pop();
Integer b = st.pop();
st.push(b - a);
} else
if (s.equals("*"))
{
Integer a = st.pop();
Integer b = st.pop();
st.push(a*b);
} else
if (s.equals("/"))
{
Integer a = st.pop();
Integer b = st.pop();
st.push(b/a);
} else
st.push(Integer.parseInt(s));
}
System.out.println(st.peek());
con.close();
}
}
Python реализация
Читаем
входную строку – выражение в Обратной Польской Записи.
lst = input().split()
Объявим стек s.
s = []
Обрабатываем
термы до конца списка lst.
for v in lst:
Обрабатываем
четыре арифметические операции.
if v == '+':
a = s.pop()
b = s.pop()
s.append(a + b)
elif v == '-':
a = s.pop()
b = s.pop()
s.append(b - a)
elif v == '*':
a = s.pop()
b = s.pop()
s.append(a * b)
elif v == '/':
a = s.pop()
b = s.pop()
s.append(b // a)
else:
Терм v является числом. Преобразуем его из строкового
представления в число и заносим в стек.
s.append(int(v))
Выводим
результат выражения, который находится на вершине стека.
print(s.pop())