|
Вопрос # 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: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, 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:26 [#18]:
Надо экспериментировать, может быть что то я не так придумал.
Галочка "подтверждения прочтения" - вселенское зло.
|
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
