Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »



Вопрос # 2 843

/ вопрос открыт /

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

Владимир Александрович Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: Владимир Александрович (статус: Посетитель)
Вопрос отправлен: 26 мая 2009, 18:37
Состояние вопроса: открыт, ответов: 0.


Мини-форум вопроса

Всего сообщений: 18; последнее сообщение — 28 мая 2009, 17:26; участников в обсуждении: 2.
Вадим К

Вадим К (статус: Академик), 26 мая 2009, 18:43 [#1]:

Без использования парсера? никак. парсер по любому нужен.
Вы бы хотя бы привели пример входных и выходных данных...
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 26 мая 2009, 19:34 [#2]:

Ну можно же как то обойти парсер. Ну там просматривать строки. А потом заносить в стек(список) или в массив. Вот пример входных данных: 56 89 + 19 * 45 -
И должно получится что-то типа того: ((56+89)*19-45).
Если чем-то поможет я могу выложить код программы преобразования, инфиксной нотации в постфиксную запись.
Вадим К

Вадим К (статус: Академик), 26 мая 2009, 23:44 [#3]:

Я даже не знаю, как Вы умудрились реализовать перевод инфиксной записи в постфиксную без парсера. Это невозможно. Потому что тот код, который может делать подобный перевод уже есть парсер.
Алгоритм в принципе прост.
читаем строку по лексемам.
если число - кладем в стек
если операция - достаем с стека два верхних и кладем в стек такое '('+ первое_со_стека + операция + второе_со_стека +')'.
Как только входная строка пустая - на вершине стека лежит готовая строка. И в стеке должно быть только один элемент.
Но в этого алгоритма есть один недостаток - он не анализирует, нужны ли скобки и лепит их по максимуму.
Это можно тоже обойти, надо только запоминать предыдущую операцию и немножко поменять политику "наложения скобок".
идея такая
читаем строку по лексемам.
если число - кладем в стек
если операция - достаем с стека два верхних и кладем в стек такое '('+ первое_со_стека+')' + операция + второе_со_стека , если текущая операция более приоритетная. Если нет, то без скобок.

Надеюсь, что у нас совпадет понятие "первое_со_стека"
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 27 мая 2009, 02:06 [#4]:

Спасибо вам за алгоритм! Вообщем я разобрался. Но со скобками не понятно как-то. Помогите дописать процедуру, пожалуйста по вашему алгоритму.

Вот код.
var
SStack:array[0..250] of string;
n,schet3,i,j:longint;

procedure DobavlenieS(x:string);
begin
inc(schet3);
SStack[schet3]:=x;
end;

function VitalkS:string;
begin
VitalkS:=SStack[schet3];
SStack[schet3]:=#0;
dec(schet3);
end;

Function prior(ch:char):byte;
begin
case ch of

'(' : Result:=0;

'+','-' : Result:=1;

'*','/' : Result:=2;

'^': Result:=3;
end;
prior:=result;
end;

function Postfix(s:string):string;
var
ss:string;
x,s1,s2:string;
operac,s3:char;
i,j:longint;
begin
i:=0;
repeat
j:=i+1;
repeat inc(i) until s[i]=' ';
ss:=copy(s,j,i-j);
operac:=ss[1];
if not(operac in ['+','-','*','/','^']) then begin
DobavlenieS(ss);
end
else begin
S2:=VitalkS;
S1:=VitalkS;
S3:=operac;
DobavlenieS('('+S1+S3+S2+')');
end;
until i>=n;
x:=VitalkS;
Postfix:=x;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
s3:=Edit4.Text;
n:=length(s3);
s4:=postfix(s3);
Edit5.Text:=s4;
end;

Пожалуйста, очень надо!
Вадим К

Вадим К (статус: Академик), 27 мая 2009, 02:36 [#5]:

Как я люблю это "очень надо". Вообще то удалять такие вопросы и таких вопрошающих.
Скомпилировал приведённый код, работает, вроде даже так, как я ожидал.
Что же хочется? минимизации скобок? это возможно. Но хочется спросить, зачем в процедуре prior, которая кстати не используется, есть вариант со скобкой? Мне кажется, что Вы плохо учили материал, ибо в противном случае знали, что в постфиксной записи скобок не может быть. По определению.
Галочка "подтверждения прочтения" - вселенское зло.
Вадим К

Вадим К (статус: Академик), 27 мая 2009, 02:38 [#6]:

Или если эта программа не работает, то приведите текстовую строку, на которой программа не работает.
И было бы неплохо сделать хоть какой то контроль (Переполнение стека, опустошение, корректность данных на конец работы)
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 27 мая 2009, 12:36 [#7]:

Вы меня немного не поняли. Программа работает. И я знаю что в постфиксной форме нет скобок. Мне просто надо при переводе из постфиксной формы записи в инфиксную избавится от лишних скобок.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 27 мая 2009, 19:06 [#8]:

Очень очень надо!
Вадим К

Вадим К (статус: Академик), 27 мая 2009, 19:23 [#9]:

не стоит писать "очень надо". Людям это уже давно надоело.
Реализовать разбор в одну сторону и не суметь более простой...
Переделывать надо в этой части
else begin
S2:=VitalkS;
S1:=VitalkS;
S3:=operac;
DobavlenieS('('+S1+S3+S2+')');
end;
она должна быть где то такой
else begin
S2:=VitalkS;
S1:=VitalkS;
S3:=operac;
if (prior(s3[1]) > priorpred)
  DobavlenieS('('+S1+')'+S3+S2)
else
  DobavlenieS(S1+S3+S2);
priorpred := prior(s3[1]);
end;
и где то в начале инициализация
var 
  priorpred:integer;
//...
priorpred :=maxint; //делаем так, что бы первый аргрумент на заворачивало в скобки
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 28 мая 2009, 01:18 [#10]:

Спасибо! И последний вопрос. Как написать процедуру, чтоб просматривалась строка и если после числа стоит операция то вставить пробел(между знаком и операцией) и если после операции стоит операция, вставить пробел между операцией и операцией!
Владимир Александрович

Владимир Александрович (статус: Посетитель), 28 мая 2009, 01:48 [#11]:

А и еще одно почему это не работает для строки типа 2 3 8 + *
Вадим К

Вадим К (статус: Академик), 28 мая 2009, 10:16 [#12]:

Как понимать "почему не работает"? выводит что то не так, выдает ошибку?
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 28 мая 2009, 10:29 [#13]:

Пишет (2)*3+8
Вадим К

Вадим К (статус: Академик), 28 мая 2009, 11:15 [#14]:

значит напутали с приоритетами и начальным значением. Код в студию, разберём.
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 28 мая 2009, 12:38 [#15]:

Использовал ваш код. Вот.
function Postfix(s:string):string;
var
ss:string;
x,s1,s2:string;
operac,s3:char;
i,j:longint;
begin
i:=0;
repeat
j:=i+1;
repeat inc(i) until s[i]=' ';
ss:=copy(s,j,i-j);
operac:=ss[1];
if not(operac in ['+','-','*','/','^']) then begin
DobavlenieS(ss);
end
else begin
S2:=VitalkS;
S1:=VitalkS;
S3:=operac;
if (prior(s3)>priorpred) then DobavlenieS('('+s1+')'+s3+s2)
else DobavlenieS(S1+S3+S2);
priorpred:=prior(s3);
end;
until i>=n;
x:=VitalkS;
Postfix:=x;
end;


priorpred:=maxint;

Для выражений типа 2 3 + 6 * работает правильно! Для выражений типа 2 3 6 + * работает неправильно и вообще если операндов подряд стоят больше трех работает не правильно. А если поменять местами S1 и S2, то получается наоборот для двух подряд стоящих операндов работает не правильно для более или равным 3 работает правильно!
Вадим К

Вадим К (статус: Академик), 28 мая 2009, 13:03 [#16]:

А первоначальный вариант, который скобки ставит по максимуму, правильно раставляет скобки?
Галочка "подтверждения прочтения" - вселенское зло.
Владимир Александрович

Владимир Александрович (статус: Посетитель), 28 мая 2009, 17:20 [#17]:

Первоначальный вариант да, все правильно расставляет.
Вадим К

Вадим К (статус: Академик), 28 мая 2009, 17:26 [#18]:

Надо экспериментировать, может быть что то я не так придумал.
Галочка "подтверждения прочтения" - вселенское зло.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.

Версия движка: 2.6+ (26.01.2011)
Текущее время: 26 сентября 2020, 04:12
Выполнено за 0.02 сек.
Рейтинг@Mail.ru