Матч 348, Потерянные скобки (LostParentheses)

Дивизион 2, Уровень 2

Имеется арифметическое выражение, содержащее положительные числа, знаки ‘+’, ‘-‘ и скобки. Затем скобки стерли. Необходимо определить минимальное значение, которое могло иметь исходное арифметическое выражение.

Класс: LostParentheses

Метод: int minResult(string e)

Ограничения: e содержит от 1 до 50 символов ‘0’ – ‘9’, ‘+’, ‘-’, первый и последний символы e являются цифрами.

Вход. Строка e, содержащая арифметическое выражение без скобок.

Выход. Наименьшее значение, которое может иметь арифметическое выражение, если в нем расставить скобки.

Пример входа

e

“55-50+40”

“10+20+30+40”

“00009-00009”

Пример выхода

-35

100

0

РЕШЕНИЕ

обработка строк + математика

Если выражение, содержащееся в строке e, содержит только операции сложения, то результатом будет сумма всех чисел выражения. Иначе всегда можно расставить скобки так, что все числа, следуемые после первой операции вычитания, будут отниматься. Например, для выражения

4 + 3 – 4 – 3 + 6 + 4 – 5 + 3 – 3

скобки можно расставить так:

4 + 3 – 4 – (3 + 6 + 4) – (5 + 3) – 3

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

ПРОГРАММА

#include <cstdio>

#include <string>

#include <sstream>

using namespace std;

class LostParentheses

{

public:

int minResult(string e)

{

int neg = 0, res, n;

char sign;

stringstream in(e);

in >> res;

while(in >> sign)

{

in >> n;

if (sign == '-') neg = 1;

if (neg) res -= n; else res += n;

}

return res;

}

};