Не знаю нужно ли это, примера выше вполне хватает. Но если нужен лексический анализ посложнее, то используем теорию(обращатся на http://www.softcraft.ru)
Сначала придумывал реги:

Код

operator:=[+-*/%] number:=(([0-9]*\.)?[0-9]+)|([0-9]+(\.[0-9]*)?)

Затем нарисовал по ним граф(по диаграме Вирта). ДКА строил ручками по нарисованному графу, в уме создавал множества first/follow. Для такой маленькой таблички это еще возможно, при более сложной грамматике юзаем соответствующие инструменты(GOLDParser, flex и т.п.)

Код

//вводим классы для удобства litera.WSPACE=0; litera.NUMBER=1; litera.POINT=2; litera.OPERATOR=3 litera.EOF=4; litera.UNKNOWN_LIT=5; function litera(sym) { //транслитератор, преобразовываем символы к классам выше  if(sym<=" ") return litera.WSPACE;  if(sym>="0"&&sym<="9") return litera.NUMBER;  if(sym==".") return litera.POINT;  if("+-*/%".indexOf(sym)>=0) return litera.OPERATOR;  return litera.UNKNOWN_LIT; } var dka=[ //собственно сама таблица ДКА  [ 0,-1, 6, 6, 6, 6], //wspace  [ 3, 2, 2, 3, 5, 5], //number  [ 1,-1,-1, 4,-1,-1], //point  [ 7,-1, 6, 6, 6, 6],  //operator  [-2,-1, 6, 6, 6, 6] //end of string ]; function dkaParser(str) { //ну и простой разбор  var ret=[];  var state=0, lt, c, i=0, numbuf="";  while(true) { //прерывание цикла по автомату        lt = (i<str.length)? litera(c=str.charAt(i)): litera.EOF; //достаём класс символа if(lt>dka.length) throw "Parse error: illigal character: "+c+", at position: "+i; state=dka[lt][state]; //делаем переход        //расбор состояний автомата if(state==0) i++; else if(state>=1 && state<=5) {numbuf+=c; i++; } else if(state==6) {ret.push({type:"number", val:parseFloat(numbuf)}); numbuf=""; state=0;} else if(state==7) {ret.push({type:"operator", val:c}); i++; state=0;} else if(state=-2) break; else throw "Parse error unknown token at position: "+i;  }  return ret; } var p=dkaParser("2*3+3*2"); //получаем массив лексем for(var i=0; i<p.length; i++) {  alert(p[i].type+": "+p[i].val); }

Состояния 6 и 7 не внесенны в таблицу, мы просто устанавливаем начальное состояние вручную state=0
Цикл разбора бесконечный, прерывается автоматом, потому за ним нужно хорошо следить, а то можешь уйти в бесконечный цикл
Для парсинга числа я использовал parseFloat, ты можешь при получении числа вторично пройтись по нему и распарсить встроенными функциями, либо парсить на состояниях 1-5


Это была лексика, теперь нужно это всё собрать до четвёрок либо любого другого представления со всеми возможными вариантами раставления скобок. Затем всё выполнить, найти требуемый результат и выбрать наиболее подходящее выражение.

Прикольно. С такой теорией любая олимпиада = "нефиг нафиг пофиг" . Пока поизучаю. Придумаете еще - буду рад. пока что - сенькс.

Цитата(Sardar @ 11.2.2005, 23:19)

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

количество комбинаций расстановки скобок конечно, поэтому количество всевозможных значений выражения конечно, а значит, из них можно выбрать максимум
с операциями типа % действительно проблема - зависимость не монотонна по аргументам, там так не получится...

В условии такех вообще не имеется. Я решил попробовать грузить цифры в один массив, а знаки в другой. Изменяем массив со знаками, сливаем, проверяем на макс, сохр. копию, идем дальше...
Но, хр-вато как-то

А действительно. Так как "+" и "-" равнозначны, то смысл есть только относительно "*" скобки ставить, больше они нигде роли не играют. Надеюсь. Если неправ, то скажите.

Цитата

Так как "+" и "-" равнозначны, то смысл есть только относительно "*" скобки ставить, больше они нигде роли не играют. Надеюсь. Если неправ, то скажите.

(1-2)+3
1-(2+3)

Уже догадался. Обломчик.
Добавлено @ 21:32
Задолбался. Не могу заставить ету штуку все варианты строить. Тут нужна рекурсия или псевдорек., что-то вообще ничего не получается. Хоть словами опишите алгор. Извиняюсь за ламерство.

Блин сижу и гадаю как порешать, никогда таким не занимался, алгоритм придумал сам, так что извиняюсь за глупости Отсюда вывод, надо читать теорию!
Хранить все деревя выражения крайне не эффективно, ибо всю память сожрёт.

Вот что я надумал, может завтра выложу код:

Код

1+2+3+4+5+6 level 1: (1+2)+3+4+5+6 1+(2+3)+4+5+6 (1+2)+(3+4)+5+6 1+2+(3+4)+5+6 (1+2)+3+(4+5)+6 1+(2+3)+(4+5)+6 (1+2)+(3+4)+(5+6) level 2: (R1+3)+4+5+6 R1+(3+4)+5+6 (R1+3)+(4+5)+6 R1+3+(4+5)+6 (R1+3)+4+(5+6) R1+(3+4)+(5+6) R1+3+4+5+6

Сначала убираем все приоритеты операций, мы расставляем все скобки. Заводим для каждого уровня дерева целый счётчик, присваиваем ему 1. Считаем сколько в выражении чисел, делим на два, вот это максимальная разрядность счётчика. В примере это 3 бита.

Взяли значение счётчика текущего уровня, раскладываем на биты и идём вдоль битового ряда и ряда чисел нашего выражения. Если бит равен 0, то пропускаем число, иначе обьеденяем текущее число и следующее в ноду Ri.

Переходим на уровень выше, повторяем действия выше. Так продолжается до корня. Вычисляем выражение, это очень просто если ты строил дерево на обéктах операторах, тогда вызываем у корня выполнить, а тот в свою очередь рекурсивно опросит потомков и так до самых листьев. Если пишем не на обьектно ориентированном языке, то строим линейное дерево на тройках, такое представление очень легко вычислить.

Посчитали, сохранили где нибудь результат + все счётчики с уровней. Таким образом мы можем сравнить результаты и если надо, востановить дерево. Построенное и уже не нужное дерево удаляем, освобождая память под следующее дерево.

Инкрементируем счётчик первого уровня и повторяем все действия снова. Как только счётчик первого уровня переполнится, инкрементируем счётчик второго уровня, по такому правилу и выше по дереву.

Посчитали, ОК, теперь всё по новой, но связывать узлы по счётчику будем не слева на право, а с права на лево. Последнее дерево можно не генерить, оно такое же как и при первой половине вычислений.


Всё посчитали, теперь достаём нашь своп файл и т.п. куда мы сохраняли результаты вычисления дерева и счётчики. Находим тот результат, который нужен(наибольший, наименьший, по указанию васи пупкина...). Отсюда находим все вариации деревьев которые дают этот результат. По счётчикам ставим скобки точно также как строили деревья.

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

теперь будем думать: нам нужен быстрый алгоритм или алгоритм с неболшим использованием памяти?
1. небольшое использование памяти: тогда рекурсия, максимальное использованием памяти - приблизительно N*Length(s)/2
2. скорость: дело в том, что алгоритм можно ускорить, пожертвовав некоторым объемом памяти, получается так, что граф разбора деревом не является (точнее не совсем является), т.к. выражения:
(1+1)-(2+2) (первая операция - над 1-цами)
и
(1+1)-(2+2) (первая операция - над 2-ками)
логично было бы считать одинаковыми (а тогда уже и обрабатывать один раз)
но к ним можно прийти двумя путями, а значит, это не дерево
вот на отказе от повторной обработки и получится ускорение
но для этого надо хранить все результаты обработки каждого такого выражения (вот и наша жертва - память)

Права пословица, утром голову глючит меньше чем вечером
Дерево можно не строить! На каждом уровне мы имеем ряд чисел, все связанные узлы вычисляем и получаем новый ряд, в котором как миннимум на одно число стане меньше. Над новым рядом повторяем те же операции и опять вычисляем узлы. Так до тех пор пока в ряду не останется всего одно число, которое и будет результатом.

Количество счётчиков равно высоте самого высокого дерева, т.е. N-1, где N это количество чисел в выражении. Самое низкое дерево получаем если обьеденяем как можно больше пар из соседних элементов.
Добавлено @ 11:04
Дерево точно можно не строить, извиняюсь если не ясно описал, попробую обьяснить кодом вечером, сейчас я на работе, перерыв

Если усложним задачу: в выражении могут встречатся негативные числа и уже проставленные скобки: 1+-3-(45/7+12*6+9)*(-1)+34

Негативные числа распознаются парсером, он же и номрализует их до вида (- число). Мы получаем ряд готовых чисел. По грамматике разбора генерим в конце выражение назад.

Уже существующие скобки убирать нельзя. Тогда мы вычилсяем содержимое скобок отдельно(подвыражение) и получаем множество результатов {число:счётчики}. Заменяем все вхождения выражений в скобках на Si, где для каждой Si вычислили своё множество результатов. Ну а затем работаем с текущим деревом подставляя на места Si числа из связанного множества.

Таким образом можно иметь скольугодно уже ресставленных скобок как угодно вложенных друг в друга.

Спасибо, за что есть
Буду разбираться.
Можете порекомендовать теорию по динам(или простому) программингу в электронном виде или имена авторов?

Это сообщение отредактировал(а) Fixin - 16.2.2005, 18:12

Цитата

Сначала убираем все приоритеты операций

Это как?

Цитата(Fixin @ 16.2.2005, 17:10)

Это как?

Приоритеты операций это то что ты сам реализуешь. Если этого не делать, то приоритетов не будет Звныяюсь за код, сейчас порпобую разрулить у себя и выложить что нибудь.

Цитата

Цитата  Сначала убираем все приоритеты операций Это как?

Я не понял куда убираем-то?