Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ Алгоритм вычисления выражений в постфиксной форме

Автор: blackhard 23.04.2008 22:00

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

Автор: volvo 23.04.2008 22:11

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

Автор: blackhard 23.04.2008 22:45

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

Автор: blackhard 24.04.2008 0:41

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

Автор: blackhard 24.04.2008 19:19

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

Автор: blackhard 25.04.2008 0:34

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


//строка с выражением после работы программы результат 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 25.04.2008 2:07

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

Вот тут лежит рабочая программа на Паскале: http://volvo71.narod.ru/faq_folder/postfix.htm#postf_ex_3

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

Автор: blackhard 25.04.2008 2:44

Цитата(volvo @ 24.04.2008 23:07) *

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

Вот тут лежит рабочая программа на Паскале: http://volvo71.narod.ru/faq_folder/postfix.htm#postf_ex_3

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

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

Автор: volvo 25.04.2008 3:11

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

Автор: blackhard 25.04.2008 3:19

Цитата(volvo @ 25.04.2008 0:11) *

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

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

Автор: blackhard 29.04.2008 22:46

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


#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 30.04.2008 0:11

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

Автор: blackhard 1.05.2008 4:39

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


#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 эти переменные и когда их в стек пихать )?

Автор: volvo 1.05.2008 6:28

Цитата
А вот если у меня выражение будет содержать не просто буквы a...Z или цифры 1..9 а имена переменных
По ссылке, которую я тебе давал, есть алгоритм перевода, в котором написано:
Цитата
Выpажение сканиpyется слева напpаво, пpи этом pазбиваясь на токены - числа и знаки аpифметических опеpаций.

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


Автор: blackhard 1.05.2008 14:32

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


*Stack2[Len],**ST2=Stack2


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

Автор: volvo 1.05.2008 15:03

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

Автор: Сережа 11.02.2014 7:16

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

Автор: nishaknapp 29.07.2022 18:43

Why not settling on games that is fun and at the same time your earning. Well itll make suspense because of the game as well but dude just try it and it gave me hope while pandemic is real rn. https://www.maxgameon.com/5-tips-for-beginners-to-win-in-baccarat/