Разбор математического выражения

← →
Anton_112 (2006-05-14 01:05) [0]

Задача - пользователь вводит выражение, необходимо представить его в памяти в виде двоичного дерева.
Думаю, несложно будет сделать вызывая рекурсивно процедуру добавления узла для каждого действия. В корне дерева должно находиться действие, которое при вычислении будет выполнено последним. Возникла трудность, как найти в выражении это действие. В идеале - его позицию в строке.
например:
28+3*2-(7+14)*12/3+79
при разборе должно указать на последний плюс.
28+3*2-(7+14)*12/3+79

← →
Германн © (2006-05-14 01:45) [1]

Ищи в гугле или яндексе "обратная польская запись" и да прибудет тебе успех.

← →
Anton_112 (2006-05-14 02:08) [2]

Спасибо, думаю это мне поможет. Я и начал с google, но не знал как сформулировать запрос :)

← →
Жуков Олег (2006-05-14 03:40) [3]

Показалось интересным, написал - вычисление выражения с помощью двоичного дерева. Причесать, выловить глюки и можно сдавать:
type TOperandStyle = (osNumber, osExpression); TOperand = class private FStyle: TOperandStyle; FValue: Extended; FOperand1: TOperand; FOperand2: TOperand; FAction: Char; protected function GetValue(): Extended; public property Value: Extended read GetValue write FValue; constructor Create(Expression: string); destructor Destroy(); override; end; { TOperand } function TOperand.Getvalue(): Extended; begin if FStyle = osNumber then Result := FValue else case FAction of "+": Result := FOperand1.Value + FOperand2.Value; "-": Result := FOperand1.Value - FOperand2.Value; "*": Result := FOperand1.Value * FOperand2.Value; "/": Result := FOperand1.Value / FOperand2.Value; else raise Exception.Create("Unknown action."); end; end; constructor TOperand.Create(Expression: string); var Index: Integer; BracketCount: Integer; OperandExpression1, OperandExpression2: string; PassNumber: Integer; Completed : Boolean; begin inherited Create(); FStyle := osNumber; Expression := Trim(Expression); if Expression[1] = "(" then if Pos(")", Expression) = Length(Expression) then Expression := Copy(Expression, 2, Length(Expression) - 2); Completed := False; PassNumber := 1; while (PassNumber <= 2) and not Completed do begin BracketCount := 0; OperandExpression1 := ""; OperandExpression2 := ""; Index := Length(Expression); while (Index > 0) and not Completed do begin case Expression[Index] of ")": begin Inc(BracketCount); end; "(": begin Dec(BracketCount); end; "+", "-", "*", "/": if (BracketCount = 0) and ((Expression[Index] in ["+", "-"]) or (PassNumber = 2)) then begin FStyle := osExpression; FOperand2 := TOperand.Create(OperandExpression2); OperandExpression1 := Copy(Expression, 1, Index - 1); FOperand1 := TOperand.Create(OperandExpression1); FAction := Expression[Index]; Completed := True; end; end; OperandExpression2 := Expression[Index] + OperandExpression2; Dec(Index); end; // while Index < Length(s) do Inc(PassNumber); end; if FStyle = osNumber then begin FValue := StrToFloat(Expression); end; end; destructor TOperand.Destroy(); begin if Assigned(FOperand1) then FOperand1.Destroy(); if Assigned(FOperand2) then FOperand2.Destroy(); inherited; end; procedure TForm1.Button1Click(Sender: TObject); var Operand: TOperand; begin Operand := TOperand.Create(Edit1.Text); try Edit2.Text := FloatToStr(Operand.Value); finally Operand.Free(); end; end;

← →
TUser © (2006-05-14 07:28) [4]

http://algolist.manual.ru/syntax/index.php

← →
Anton_112 (2006-05-15 00:26) [5]

Спасибо, работа на день останавливалась ,но с помощью обратной польской записи задачу почти решил. К тому же спасибо за приведенное здесь решение.
Возник вопрос - можно смело полагать ,что действие, оказавшееся в обратной польской записи последним, и должно выполняться последним в выражении? Просто этот алгоритм раньше был мне неизвестен, и пока что я не смог до конца понять его.

← →
Германн © (2006-05-15 01:15) [6]

> Возник вопрос - можно смело полагать
> ,что действие, оказавшееся
> в обратной польской записи последним, и должно выполняться
> последним в выражении? Просто этот алгоритм раньше был мне
> неизвестен, и пока что я не смог до конца понять его.

Этот алгоритм - "классика жанра". Так что можно "смело полагаться на него", но вот на конкретную реализацию полагаться не следует. Её нужно тщательно проверять.

← →
Anton_112 (2006-05-15 02:26) [7]

Увы, реализовал его с использованием стека ,и на одной из простых проверок он выдал неверный результат... Хотелось бы закончить самаому, но время поджимает, поэтому вопрос к Жукову Олегу, не могли бы вы словами хотя бы вкратце рассказть как разделяете строку с выражением на OperandExpression1 и OperandExpression2? Просмотрев исходник я боюсь что не до конца понял ваш подход.
P.S: Извините за настойчивость

← →
Жуков Олег (2006-05-15 02:56) [8]

> Anton_112 (15.05.06 02:26) [7]

Там всё просто - идём по строке от последнего символа к первому, как только встречаем знак "-" или "+" вне скобок (это соответсвует BracketCount = 0), значит всё, что справа - Expression2, а всё что слева - Expression1 (кстати, можно оптимизировать код по скорости, если Expression2 выделять именно в этот момент, а не прибавлять посимвольно на каждом витке цикла). Тогда разбор строки завершается, запоминается действие, и дальнейший разбор поручается дочерним Operand1 и Operand2,. Если же в первом проходе не обнаружено знаков "+" или "-", запускается второй такой-же проход, в котором точно так же ищется уже знак "*" или "/" (PassNumber=2, здесь тоже можно ускорить, если запоминать позицию знака в дополнительную переменную в первом проходе, тогда можно обойтись одним проходом). Ну а дальше дочерние операнды сами разруливают переданные им выражения, и строят дерево вниз. Если в строке не обнаружено знаков "+", "-", "*", "/", то считается, что это просто число. Ещё там можно выкинуть Completed, его проверка заменяется на FStyle = osExpression.

← →
Anton_112 (2006-05-15 15:24) [9]

Спасибо, я сам придумал похожий алгоритм, но этот выглядит "элегантнее".
Благодарю.

← →
StymPunk (2006-05-31 23:54) [10]

> Anton_112

Здравствуйте,
Вы не могли бы скинуть мне свою програмку на мыло? :-)

← →
Joker007 (2006-06-18 23:23) [11]

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

← →
Германн © (2006-06-19 02:16) [12]

> Joker007 (18.06.06 23:23) [11]
>
> Если вы еще тут, не могли бы вы рассказать поподробнее о
> работе своей программки – что происходит с выражением после
> того, как пользователь вводит выражение.

А рассказать нужно "с выражением"? :-)

← →
Joker007 (2006-06-19 12:22) [13]

Было бы неплохо :-)))

> Возник вопрос - можно смело полагать ,что действие, оказавшееся
> в обратной польской записи последним, и должно выполняться
> последним в выражении?

Не должно, а может - одно и тоже выражение можно записать в виде разных обратных польских записей.

> Не должно, а может - одно и тоже выражение можно записать
> в виде разных обратных польских записей.

Объясни, пожалуйста. Что, как и почему?

1+2+3 может быть записано как 1 2 + 3 + или как 2 3 + 1 +. Соотвественно, какой плюс выполнится последним - зависит от алгоритма разбора.

> Соотвественно, какой плюс выполнится последним - зависит
> от алгоритма разбора.

Это преобразование выражения. Алгоритм разбора должен выдавать оригинальный порядок.

Разбор математического выражения Найти похожие ветки