| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Разбор математического выражения
Anton_112 © (2006-05-14 01:05:00)Задача - пользователь вводит выражение, необходимо представить его в памяти в виде двоичного дерева.
Думаю, несложно будет сделать вызывая рекурсивно процедуру добавления узла для каждого действия. В корне дерева должно находиться действие, которое при вычислении будет выполнено последним. Возникла трудность, как найти в выражении это действие. В идеале - его позицию в строке.
например:
28+3*2-(7+14)*12/3+79
при разборе должно указать на последний плюс.
28+3*2-(7+14)*12/3 +79
atruhin (2006-06-20 05:55:00) [1]> Соотвественно, какой плюс выполнится последним - зависит
> от алгоритма разбора.
Это преобразование выражения. Алгоритм разбора должен выдавать оригинальный порядок.
TUser (2006-06-20 03:30:00) [2]1+2+3 может быть записано как 1 2 + 3 + или как 2 3 + 1 +. Соотвественно, какой плюс выполнится последним - зависит от алгоритма разбора.
Германн (2006-06-20 02:23:00) [3]
> Не должно, а может - одно и тоже выражение можно записать
> в виде разных обратных польских записей.
Объясни, пожалуйста. Что, как и почему?
TUser (2006-06-19 12:49:00) [4]
> Возник вопрос - можно смело полагать ,что действие, оказавшееся
> в обратной польской записи последним, и должно выполняться
> последним в выражении?
Не должно, а может - одно и тоже выражение можно записать в виде разных обратных польских записей.
Joker007 (2006-06-19 12:22:00) [5]Было бы неплохо :-)))
Германн (2006-06-19 02:16:00) [6]
> Joker007 (18.06.06 23:23) [11]
>
> Если вы еще тут, не могли бы вы рассказать поподробнее о
> работе своей программки – что происходит с выражением после
> того, как пользователь вводит выражение.
А рассказать нужно "с выражением"? :-)
Joker007 (2006-06-18 23:23:00) [7]Если вы еще тут, не могли бы вы рассказать поподробнее о работе своей программки – что происходит с выражением после того, как пользователь вводит выражение.
StymPunk (2006-05-31 23:54:00) [8]
> Anton_112
Здравствуйте,
Вы не могли бы скинуть мне свою програмку на мыло? :-)
Anton_112 (2006-05-15 15:24:00) [9]Спасибо, я сам придумал похожий алгоритм, но этот выглядит "элегантнее".
Благодарю.
Жуков Олег (2006-05-15 02:56:00) [10]
> 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 02:26:00) [11]Увы, реализовал его с использованием стека ,и на одной из простых проверок он выдал неверный результат... Хотелось бы закончить самаому, но время поджимает, поэтому вопрос к Жукову Олегу, не могли бы вы словами хотя бы вкратце рассказть как разделяете строку с выражением на OperandExpression1 и OperandExpression2? Просмотрев исходник я боюсь что не до конца понял ваш подход.
P.S: Извините за настойчивость
Германн (2006-05-15 01:15:00) [12]
> Возник вопрос - можно смело полагать
> ,что действие, оказавшееся
> в обратной польской записи последним, и должно выполняться
> последним в выражении? Просто этот алгоритм раньше был мне
> неизвестен, и пока что я не смог до конца понять его.
Этот алгоритм - "классика жанра". Так что можно "смело полагаться на него", но вот на конкретную реализацию полагаться не следует. Её нужно тщательно проверять.
Anton_112 (2006-05-15 00:26:00) [13]Спасибо, работа на день останавливалась ,но с помощью обратной польской записи задачу почти решил. К тому же спасибо за приведенное здесь решение.
Возник вопрос - можно смело полагать ,что действие, оказавшееся в обратной польской записи последним, и должно выполняться последним в выражении? Просто этот алгоритм раньше был мне неизвестен, и пока что я не смог до конца понять его.
TUser (2006-05-14 07:28:00) [14]http://algolist.manual.ru/syntax/index.php
Жуков Олег (2006-05-14 03:40:00) [15]Показалось интересным, написал - вычисление выражения с помощью двоичного дерева. Причесать, выловить глюки и можно сдавать:
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;
Anton_112 (2006-05-14 02:08:00) [16]Спасибо, думаю это мне поможет. Я и начал с google, но не знал как сформулировать запрос :)
Германн (2006-05-14 01:45:00) [17]Ищи в гугле или яндексе "обратная польская запись" и да прибудет тебе успех.
| |
