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

> Внимание!

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

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

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


Бывалый
***

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

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


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


Гость






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


Бывалый
***

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

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


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


Бывалый
***

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

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


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


Бывалый
***

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

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


Вобщем я сделал так сначало превожу выражения из инфиксной формы в постфиксную а потом вычисляю получившееся выражение в постфиксной форме.Это единственный способ вычисления инфиксных выражений?Или есть более простой?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






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

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

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


Бывалый
***

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

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


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

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

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

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

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


Гость






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


Бывалый
***

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

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


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

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

Все спасибо теперь я знаю в чем точно ошибка (надеюсь единственная) я запоминал ранг операции которую заносил в стек, а ведь насамом деле надо просто посмотреть че лежит сверху без выталкивания.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Цитата
Рабочий алгоритм перевода из инфиксной формы в постфиксную
С каких пор программа, не проходящая компиляцию (GCC), является "рабочей", можно уточнить?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






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

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

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


Бывалый
***

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

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


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

*Stack2[Len],**ST2=Stack2


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

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


Гость






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


Гость






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


Бывалый
***

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

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


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. 5 Tips For Beginners To Win In Baccarat
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 28.03.2024 16:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name