Алгоритм вычисления выражений в постфиксной форме, Си Опции

[blackhard]

Может кнонибудь подсказать алгоритм вычисления выражения(из строки) записанного в постфиксной форме.
Для выражений в инфиксной форме я знаю алгоритм а вот для постфиксной чето никак не соображу .
Напишите просто на словах что запихиваем в стек что и когда вынимаем и тд...

[volvo]

На практике вычисление постфиксных выражений реализуется с применением стека. В этом случае вычисления выполняются по следующим правилам.
1. Прочитать очередной токен входной цепочки.
2. Если входной токен - операнд, то выполнить его запись в стек.
3. Если входной токен - оператор, то прочитать два операнда из стека, выполнить операцию и результат занести в стек как операнд.
4. Повторять п.1, пока во входной цепочке не будут прочитаны все токены.

[blackhard]

Блин я вдруг понял что мнеб и для инфиксной формы алгоритм не помешал где можно почитать?

[blackhard]

Ну ктонибудь помогите пожалуйста!!!!!!!!

[blackhard]

Вобщем я сделал так сначало превожу выражения из инфиксной формы в постфиксную а потом вычисляю получившееся выражение в постфиксной форме.Это единственный способ вычисления инфиксных выражений?Или есть более простой?

[blackhard]

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

//строка с выражением после работы программы результат ab+lb/e-e* очевидно не правильно
char p[]="(a+b)*l/b-e",*po=p,c,*o,*s,t;

char Stack[Len],*ST=Stack;
//для записи в стек
char *PtoS( char c)
{
	*(++ST)=c;
	return ST;
}
//для извлечения из стека
char *PoP(void)
{
	char *c0;
	    c0=ST;
	    ST--;
		return c0;
}
int main()
{	 
PtoS('('); 

while(*po)
{
 
  if( *po=='+'||*po=='-')i=1;
  if( *po=='*'||*po=='/')i=2;
  if(isalpha(*po))printf("%c",*po);
  if((*po=='+'||*po=='-'||*po=='*'||*po=='/'||*po=='(')&&(i>k||i==k))
  {
      if( *po=='+'||*po=='-')k=1;
      if( *po=='*'||*po=='/')k=2;
	  PtoS(*po);
  }
    if(i<k)
	{
		printf("%c",*PoP());
		PtoS(*po);
	}
 if (*po==')')
 {   
	 while((c=*PoP())!='(')
		 printf("%c",c);
 }
  po++;

  //if(!*po)while((c=*PoP())!='(')printf("%c",c);

}
while((c=*PoP())!='(')printf("%c",c);

return 0;
}

Вроде все делал согласно алгоритму.

[volvo]

Вроде все делал согласно алгоритму.

Значит, не все...

Вот тут лежит рабочая программа на Паскале: Обpатная польская нотация

Посмотри, как она реализована. Если не получится сделать это на С - скажи, я помогу.

[blackhard]

Значит, не все...

Вот тут лежит рабочая программа на Паскале: Обpатная польская нотация

Посмотри, как она реализована. Если не получится сделать это на С - скажи, я помогу.

Спасибо за ссылку попробую разобрать программу.Ну я думаю что проблема в моей реализации это учет приоритетов команд.Нужно учитывать приоритет считанного символа и приоритет символа в вершине стека?Те если в стеке лежит ** и мы считываем из строки + то из стека достаем ** и стек будет выглядить так + ?Так как
узнать что в стеке лежат 2 *.В своей проге я учитываю только приоритет считанного символа и лежащего в вершине стека.Думаю это 1 из причин неправильной работы.

[volvo]

Те если в стеке лежит ** и мы считываем из строки + то из стека достаем ** и стек будет выглядить так + ?

Именно так, если текущий знак - "+", то пока в вершине стека лежит знак операции с бОльшим чем у "+" приоритетом надо вытаскивать значение из вершины, и заносить в строку (и тебе не надо знать, два умножения у тебя или десять занесено в стек, операция производится пока вершина стека содержит то, что тебя устраивает).

[blackhard]

Именно так, если текущий знак - "+", то пока в вершине стека лежит знак операции с бОльшим чем у "+" приоритетом надо вытаскивать значение из вершины, и заносить в строку (и тебе не надо знать, два умножения у тебя или десять занесено в стек, операция производится пока вершина стека содержит то, что тебя устраивает).

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

[blackhard]

Рабочий алгоритм перевода из инфиксной формы в постфиксную(Может комуто понадобится).

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define Len 2056
#define NAME 5
#define COM 4
#define MCOM 8



char per[Len]="(a+b)*(c-d)/(e*(q-w))",*pe=per,*pe2=pe,c;


char Stack[Len],*ST=Stack;

int i=0,k=0,m;


int precedence(char symb)
{
	switch(symb)
	{
		case ')':return -1;
	    case '(':return 0;
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		//default : return -1;
	}
}


int main()
{	 

*ST='(';
while(*pe)
{
	if (isalpha(*pe))printf("%c",*pe);
	else
		if(*pe=='(')*++ST=*pe;
		else
			if(*pe==')')
			{
				while((c=*ST)!='('){ printf("%c",c);ST--;}	
				--ST;
			}
			else
				if(*pe=='+'||*pe=='-'||*pe=='*'||*pe=='/')
				{
					while(precedence(*ST)>precedence(*pe)||precedence(*ST)==precedence(*pe))
					{
						printf("%c",*ST);
						ST--;
					}
					*++ST=*pe;
				}
			   
		pe++;
				if(*pe==0)while(*ST!='(')printf("%c",*ST--);
}




return 0;
}

[volvo]

Рабочий алгоритм перевода из инфиксной формы в постфиксную

С каких пор программа, не проходящая компиляцию (GCC), является "рабочей", можно уточнить?

[blackhard]

Теперь точно рабочий

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define Len 2056
#define NAME 5
#define COM 4
#define MCOM 8
char per[Len]="(a+b)*(c-d)/(e*(q-w))",*pe=per,*pe2=per,c;//ошибка была тут *pe2=pe
char Stack[Len],*ST=Stack;

int i=0,k=0,m;
int precedence(char symb)
{
	switch(symb)
	{
		case ')':return -1;
	    case '(':return 0;
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		//default : return -1;
	}
}
int main()
{	 

*ST='(';
while(*pe)
{
	if (isalpha(*pe))printf("%c",*pe);
	else
		if(*pe=='(')*++ST=*pe;
		else
			if(*pe==')')
			{
				while((c=*ST)!='('){ printf("%c",c);ST--;}	
				--ST;
			}
			else
				if(*pe=='+'||*pe=='-'||*pe=='*'||*pe=='/')
				{
					while(precedence(*ST)>precedence(*pe)||precedence(*ST)==precedence(*pe))
					{
						printf("%c",*ST);
						ST--;
					}
					*++ST=*pe;
				}
			   
		pe++;
				if(*pe==0)while(*ST!='(')printf("%c",*ST--);
}
return 0;
}

Добавлено через 9 мин.
А вот если у меня выражение будет содержать не просто буквы a...Z или цифры 1..9 а имена переменных т.е (Ax1+num)*c-Chis.Как в таком случае реализовать перевод?Нужно будет сделать 2 стека 1для строк 2й для знаков +.-...? Как формировать элементы для помещения в стек строк(т.е как выдирать Ax1 эти переменные и когда их в стек пихать )?

Сообщение отредактировано: blackhard - 1.05.2008 0:41

[volvo]

А вот если у меня выражение будет содержать не просто буквы a...Z или цифры 1..9 а имена переменных

По ссылке, которую я тебе давал, есть алгоритм перевода, в котором написано:

Выpажение сканиpyется слева напpаво, пpи этом pазбиваясь на токены - числа и знаки аpифметических опеpаций.

Если очеpедной токен - число, не глядя пишем его в выходнyю стpокy.

Так что записывать имена переменных в стек вообще не надо... А вот как выдирать из входной строки эти имена - это подумай... В конце концов, имя переменной не может содержать в себе знаки операций и скобки (это можно считать подсказкой).

[blackhard]

Блин чето запутался.Если у меня массив строк и указатель на него

*Stack2[Len],**ST2=Stack2

Как мне в 1строку этого массива спомощью указателя записать символы?

Сообщение отредактировано: blackhard - 1.05.2008 10:43

[volvo]

Ну, пока у тебя не массив строк, а массив указателей на строки. Под сами строки еще надо выделить память...

[Сережа]

Ребят а напишите этот алгоритм на паскале пжлст