Задача на обратную польскую запись

[Horknee]

Помогите, пожалуйста, разобраться с задачей.

Заданное простое выражение, содержащее вызовы функций преобразовать в обратную польскую запись. Например, y=f(I, J+g(x+y), K*L, x(I, J), 5)+2х.

Проблема в том, что выражение может быть любое, читается либо из файла, либо ввод с клавиатуры.

Заранее, очень признателен и буду рад любой помощи.

[KingOfNothing]

Ну алгоритм такой (чтобы реализовать его надо немного времени, так что уж попытайся сам):
Алгоритм

* Пока есть ещё символы для чтения:

* Читаем очередной символ.
* Если символ является числом, добавить его к выходной строке.
* Если символ является символом функции, помещаем его в стек.
* Если символ является разделителем аргументов функции (то есть, запятая):

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

* Если символ является оператором, о1, тогда:

1) пока…

… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…

… выталкиваем верхние элементы стека c бо́льшим либо равным приоритетом в выходную строку;
2) помещаем оператор o1 в стек.

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

* Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении несогласованы скобки.

Взято отсюда - http://ru.wikipedia.org/wiki/%D0%9E%...B8%D1%81%D1%8C

[CrazyRabbit]

работает со знаками *, +, /, -, ^(возведение в степень)

procedure Init(var tos:integer);
begin
tos:=0;
end;

function Empty(tos:integer):boolean;
begin
if tos=0 then
 Empty:=true
  else
   Empty:=false;
end;

procedure Push(var stack:array of char;
	       var tos:integer;
	       x:char);
begin

   inc(tos);
    stack[tos]:=x;

end;

procedure Pop(var stack:array of char;
	      var tos:integer);
begin
 if not Empty(tos) then
  dec(tos);
end;



var stack:array[0..1000]of char;
tos,i,j,kol:integer;
s,b:string;
x:char;
begin
readln(s);
Init(tos);
for i:=1 to length(s)do
 begin
  if(ord(s[i])>=97)and(ord(s[i])<=122)then
   b:=b+s[i]
    else
    if(ord(s[i])>=48)and(ord(s[i])<=57)then
   b:=b+s[i]
    else

     if s[i]='('then
      Push(stack,tos,s[i])
       else
	if s[i]=')' then
	 begin
	  while stack[tos]<>'('do
	   begin
	    b:=b+stack[tos];
	     Pop(stack,tos);
	   end;
	    Pop(stack,tos);
	 end
	  else
	   begin
		 begin
		    if ((s[i]='+')or(s[i]='-'))and((stack[tos]='+')or(stack[tos]='-'))then
		     kol:=1
		      else
		       if ((s[i]='-')or(s[i]='+'))and((stack[tos]='*')or(stack[tos]='/')or(stack[tos]='^'))then
			kol:=1
			 else
			  if((s[i]='*')or(s[i]='/'))and((stack[tos]='*')or(stack[tos]='/')or(stack[tos]='^'))then
			   kol:=1;

		   while kol=1 do
		    begin
		    kol:=0;
		     b:=b+stack[tos];
		      Pop(stack,tos);
		       if ((s[i]='+')or(s[i]='-'))and((stack[tos]='+')or(stack[tos]='-'))then
		     kol:=1
		      else
		       if ((s[i]='+')or(s[i]='-'))and((stack[tos]='+')or(stack[tos]='-')or(stack[tos]='^'))then
			kol:=1
			 else
			  if((s[i]='*')or(s[i]='/')or(s[i]='^'))and((stack[tos]='*')or(stack[tos]='/')or(stack[tos]='^'))then
			   kol:=1;

		    end;
		    push(stack,tos,s[i]);
		    end;


	    end;
    end;
	    for i:=tos downto 1 do
	     b:=b+stack[i];
	    writeln(b);
	    end.

[Horknee]

Спасибо большое за алгоритм и за программу.)

А программа, как я понял, с функциями не работает?

[KingOfNothing]

Сообщение от Horknee

Спасибо большое за алгоритм и за программу.)

А программа, как я понял, с функциями не работает?

Нет, как я понял, только арифметические операции

[Horknee]

Сообщение от KingOfNothing

Нет, как я понял, только арифметические операции

Надо будет над функциями думать, чтобы программа отличала обычную скобку от скобки функции. Счетчики, наверное, ставить...а вот если функция в функции?

[KingOfNothing]

Кстати, вспомнил у меня есть прога с польской нотацией с функциями, только это не основная тема проги, для функции в функции не должно по идее ничего поменяться

[Horknee]

Спасибо большое)

А что значит право(лево)-ассоциированый?

[KingOfNothing]

Сообщение от Horknee

Спасибо большое)

А что значит право(лево)-ассоциированый?

Честно говоря, хз