IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> Алгоритм вычисления выражений в постфиксной форме, Си
blackhard
сообщение 23.04.2008 18:00
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


Может кнонибудь подсказать алгоритм вычисления выражения(из строки) записанного в постфиксной форме.
Для выражений в инфиксной форме я знаю алгоритм а вот для постфиксной чето никак не соображу wacko.gif .
Напишите просто на словах что запихиваем в стек что и когда вынимаем и тд...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 23.04.2008 18:11
Сообщение #2


Гость






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


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


Блин я вдруг понял что мнеб и для инфиксной формы алгоритм не помешал где можно почитать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
blackhard
сообщение 23.04.2008 20:41
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


Ну ктонибудь помогите пожалуйста!!!!!!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
blackhard
сообщение 24.04.2008 15:19
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


Вобщем я сделал так сначало превожу выражения из инфиксной формы в постфиксную а потом вычисляю получившееся выражение в постфиксной форме.Это единственный способ вычисления инфиксных выражений?Или есть более простой?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
blackhard
сообщение 24.04.2008 20:34
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


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

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



Вроде все делал согласно алгоритму.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 24.04.2008 22:07
Сообщение #7


Гость






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

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

Посмотри, как она реализована. Если не получится сделать это на С - скажи, я помогу.
 К началу страницы 
+ Ответить 
blackhard
сообщение 24.04.2008 22:44
Сообщение #8


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


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

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

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

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

Спасибо за ссылку попробую разобрать программу.Ну я думаю что проблема в моей реализации это учет приоритетов команд.Нужно учитывать приоритет считанного символа и приоритет символа в вершине стека?Те если в стеке лежит ** и мы считываем из строки + то из стека достаем ** и стек будет выглядить так + ?Так как
узнать что в стеке лежат 2 *.В своей проге я учитываю только приоритет считанного символа и лежащего в вершине стека.Думаю это 1 из причин неправильной работы.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 24.04.2008 23:11
Сообщение #9


Гость






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


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


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

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

Все спасибо теперь я знаю в чем точно ошибка (надеюсь единственная) я запоминал ранг операции которую заносил в стек, а ведь насамом деле надо просто посмотреть че лежит сверху без выталкивания.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
blackhard
сообщение 29.04.2008 18:46
Сообщение #11


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


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

#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;
}




 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 29.04.2008 20:11
Сообщение #12


Гость






Цитата
Рабочий алгоритм перевода из инфиксной формы в постфиксную
С каких пор программа, не проходящая компиляцию (GCC), является "рабочей", можно уточнить?
 К началу страницы 
+ Ответить 
blackhard
сообщение 1.05.2008 0:39
Сообщение #13


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


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

#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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 1.05.2008 2:28
Сообщение #14


Гость






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

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

 К началу страницы 
+ Ответить 
blackhard
сообщение 1.05.2008 10:32
Сообщение #15


Бывалый
***

Группа: Пользователи
Сообщений: 151
Пол: Мужской
Реальное имя: иван

Репутация: -  0  +


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

*Stack2[Len],**ST2=Stack2


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

Сообщение отредактировано: blackhard - 1.05.2008 10:43
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 1.05.2008 11:03
Сообщение #16


Гость






Ну, пока у тебя не массив строк, а массив указателей на строки. Под сами строки еще надо выделить память...
 К началу страницы 
+ Ответить 
Сережа
сообщение 11.02.2014 3:16
Сообщение #17


Гость






Ребят а напишите этот алгоритм на паскале пжлст
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 19.03.2024 13:56
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"