Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций +, - и *. Необходимо расставить в этом выражении скобки так, чтобы его значение стало максимально возможным.
Технические требования
Входной файл: INPUT1.TXT
Выходной файл: OUTPUT1.TXT
Формат входных данных
В первой строке входного файла INPUT1.TXT записано исходное выражение длиной не более 250 символов. Внутри чисел пробелы не допускаются. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 10 в 6 степени.
Формат выходных данных
Выходной файл OUTPUT1.TXT должен содержать две строки. В первой должно находиться максимально возможное после расстановки скобок значение полученного выражения, во второй строке - само это выражение. Если вариантов решения задачи несколько, нужно выдать любой из них.
Пример файла входных данных 1+2-3.0*4
Пример файла выходных данных ((1+2)-3)*4

Вобщем парсингом мудрить думаю муторно для олимпиады, а что еще можете предложить?

Это сообщение отредактировал(а) Fixin - 10.2.2005, 19:11

Цитата(Fixin @ 10.2.2005, 18:09)

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

Цитата(Fixin @ 10.2.2005, 18:09)

Пример файла входных данных 1+2-3.0*4 Пример файла выходных данных ((1+2)-3)*4

Что то я не понял примера

Цитата

Что то я не понял примера

если расставить скобки по-другому, получится меньший результат (по крайней мере, мне так показалось...)

Пример не проверял. Дело не в том. Как решать-то? Это первая задача и пяти. Остальные сделал. Олимпиада областная. Мне тоже кажется, что можно и отрицательное получить... но не проверял.
Добавлено @ 19:38
Тьфу, ошибся! Там максимум нужен!!!

Цитата(maxim1000 @ 10.2.2005, 18:29)

если расставить скобки по-другому, получится меньший результат (по крайней мере, мне так показалось...)

Так тоже ноль будет: (1+(2-3))*4

Извиняюсь за глупость, но что если перебрать все возможные варианты... Медленно, но верно
Строим все возможные деревья, начиная с обьеденения листьев, затем узлов. С каждой новой вариацией копируем дерево и пускаем его по альтернативному варианту.

Только перебор.

можно покрутить в таком направлении:
как бы мы не расставили скобки, какое-то действие будет выполнено последним
выделим его выбор в отдельную часть перебора
т.е. сначала сделаем простой цикл по действиям, а внутри сделаем перебор по расстановке остальных скобок
теперь рассмотрим, какое действие может быть последним:
1. + здесь все просто: нужно максимизировать то, что слева, и то, что справа, решаются эти задачи независимо
2. - здесь тоже все просто: нужно максимизировать то, что слева, и минимизировать то, что справа
3. * здесь менее приятный случай (из-за того, что в зависимости от знака одного множителя нужно либо минимизировать, либо максимизировать другой), тут можно просто решить 4 задачи: min и max первого, min и max второго, и выбрать один из 4х вариантов

Цитата

Так тоже ноль будет

да
в остальных случаях будут отрицательные результаты (меньше нуля )

Цитата(maxim1000 @ 11.2.2005, 12:04)

1. + здесь все просто: нужно максимизировать то, что слева, и то, что справа, решаются эти задачи независимо

Не факт
2*3+3*2
2*(3+3)*2

Цитата

Не факт 2*3+3*2 2*(3+3)*2

гы-гы, факт
я описывал только "внешнюю" операцию (ту, которая выполняется последней
в первом случае все, действительно, просто
во втором "внешней" операцией является умножение, так что используется 3-е правило
а после того, как внешняя операция разделила выражение (ну, еще не совсем выражение, скорее, выражение без скобок) на два независимых (если не считать зависимости, описанной в пункте 3), в каждом из них можно перебирать свою внешнюю операцию

На этот вопрос с программерской точки зрения знает ответ ~FOX~, он в одной из тем флейма хвастался спроси у него, может код подкинет

ЗЫ 3.0 - не совсем удачное число

maxim1000 а что если выражение может быть сколь угодно большим, операции: +, -, *, /, %(модуль), -(унарный минус). Какова логика теперь?

перебор. Чистый. Это классическая задача.

Но для перебора нужны кие-то ограничения.

Основная проблема, как организовать разбор выражения по-проще, вставить-то скобки потом можно.
Добавлено @ 11:35
И еще. Может пробовать расставить скобки по каждому знаку действия?

Цитата(Fixin @ 12.2.2005, 10:33)

как организовать разбор выражения по-проще

Дык это регулярные выражения(можно LL(1) разбор). Делаешь лексический анализ на табличноуправляемом ДКА, получил числа и операторы(лексемы). Затем по лексемам собираешь деревья выражений, это по разному сделать можно. Если нужно как можно проще и изменятся в будущем особо не будет, то закодируй в ручную лексер. Приемр на JS за 5 минут:

Код

//разбор возвращает массив лексем function simpleLexer(str) {  var ret=[], c, l;  for(var i=0; i<str.length; i++) {     c=str.charAt(i);  if((c>="0"&&c<="9")||c==".") {    l=getNumber(str, i);    if(l.type=="error") throw "Parse error at "+i+", wrong syntax of number";    else ret.push(l);  } else if("+-*/".indexOf(c)>=0) {     l={type:"operator", val:c}; //при условии что у нас все операторы односимвольные  ret.push(l);  } //всё остальное просто игнорируем  }  return ret; } //достать число, я исользую встроенный parseFloat, ты же здесь можешь его распарсить function getNumber(str, j) {  var ret="", fnum=false, gotval=false;  for(var i=j; i<str.length; i++) {   if(str.charAt(i)==".") {     if(!fnum) { ret+="."; fnum=true;}     else return {type:"error",val:""}; //564.546. error   } else if(str.charAt(i)>="0"&&str.charAt(i)<="9") {ret+=str.charAt(i); gotval=true;}      else if(!gotval) return {type:"error",val:""}; //. error   else return {type:"number", val:parseFloat(ret)};  }  if(!gotval) return {type:"error",val:""}; //. error  else return {type:"number", val:parseFloat(ret)}; } //пример var p=simpleLexer("2*3+3*2"); for(var i=0; i<p.length; i++) {  alert(p[i].type+": "+p[i].val); }

С табличноуправляемым разбором покажу попозже.