польская инверсная запись. Помогите с алгоритмом.

@Matrix · Регистрация: 01.03.2010

Author24 — интернет-сервис помощи студентам

Не знаю как организовать алгоритм польской инверсной записи на С++. Если кто-то знает помогите пожалуйста.

@mik-a-el · 28.11.2007, 18:39

Пример:

Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.

Например, выражение

(6+8)*5-6/2

в польской инверсной записи имеет вид

6 8 + 5 * 6 2 / -

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

S = < >; <6>; <6,8>; <14>; <14,5>; <70>;
<70,6>; <70,6,2>; <70,3>; <67>.

Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 - операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l.

Код

    float eval (float *m, int l)
    { int p,n,i;
      float stack[50],c;
       for(i=0; i < l ;i++)
       if ((n=m[i])<0)
         {  c=st[p--];
            switch(n)
            { case -1:  stack[p]+=c;  break;
              case -2:  stack[p]-=c;  break;
              case -3:  stack[p]*=c;  break;
              case -4:  stack[p]/=c;
            }
         }
       else stack[++p]=n;
       return(stack[p]);
    }

@Matrix Now I Matrix 137 / 134 / 28 Регистрация: 01.03.2010 Сообщений: 223
		1
	польская инверсная запись. Помогите с алгоритмом. 28.11.2007, 18:30. Показов 8905. Ответов 1 Метки нет (Все метки) Не знаю как организовать алгоритм польской инверсной записи на С++. Если кто-то знает помогите пожалуйста. 0

@mik-a-el Администратор 83618 / 52196 / 244 Регистрация: 10.04.2006 Сообщений: 13,426
	28.11.2007, 18:39	2
	Пример: Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией. Например, выражение (6+8)5-6/2 в польской инверсной записи имеет вид 6 8 + 5 6 2 / - Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид S = < >; <6>; <6,8>; <14>; <14,5>; <70>; <70,6>; <70,6,2>; <70,3>; <67>. Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 - операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l. Код float eval (float m, int l) { int p,n,i; float stack[50],c; for(i=0; i < l ;i++) if ((n=m[i])<0) { c=st[p--]; switch(n) { case -1: stack[p]+=c; break; case -2: stack[p]-=c; break; case -3: stack[p]=c; break; case -4: stack[p]/=c; } } else stack[++p]=n; return(stack[p]); } 0