Форум «Всё о Паскале» _ Другие языки _ Алгоритм вычисления выражений в постфиксной форме
Автор: blackhard 23.04.2008 18:00
Может кнонибудь подсказать алгоритм вычисления выражения(из строки) записанного в постфиксной форме. Для выражений в инфиксной форме я знаю алгоритм а вот для постфиксной чето никак не соображу . Напишите просто на словах что запихиваем в стек что и когда вынимаем и тд...
Автор: volvo 23.04.2008 18:11
Цитата
На практике вычисление постфиксных выражений реализуется с применением стека. В этом случае вычисления выполняются по следующим правилам. 1. Прочитать очередной токен входной цепочки. 2. Если входной токен - операнд, то выполнить его запись в стек. 3. Если входной токен - оператор, то прочитать два операнда из стека, выполнить операцию и результат занести в стек как операнд. 4. Повторять п.1, пока во входной цепочке не будут прочитаны все токены.
Автор: blackhard 23.04.2008 18:45
Блин я вдруг понял что мнеб и для инфиксной формы алгоритм не помешал где можно почитать?
Автор: blackhard 23.04.2008 20:41
Ну ктонибудь помогите пожалуйста!!!!!!!!
Автор: blackhard 24.04.2008 15:19
Вобщем я сделал так сначало превожу выражения из инфиксной формы в постфиксную а потом вычисляю получившееся выражение в постфиксной форме.Это единственный способ вычисления инфиксных выражений?Или есть более простой?
Автор: blackhard 24.04.2008 20: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('(');
Вот тут лежит рабочая программа на Паскале: http://volvo71.narod.ru/faq_folder/postfix.htm#postf_ex_3
Посмотри, как она реализована. Если не получится сделать это на С - скажи, я помогу.
Автор: blackhard 24.04.2008 22:44
Цитата(volvo @ 24.04.2008 23:07)
Значит, не все...
Вот тут лежит рабочая программа на Паскале: http://volvo71.narod.ru/faq_folder/postfix.htm#postf_ex_3
Посмотри, как она реализована. Если не получится сделать это на С - скажи, я помогу.
Спасибо за ссылку попробую разобрать программу.Ну я думаю что проблема в моей реализации это учет приоритетов команд.Нужно учитывать приоритет считанного символа и приоритет символа в вершине стека?Те если в стеке лежит ** и мы считываем из строки + то из стека достаем ** и стек будет выглядить так + ?Так как узнать что в стеке лежат 2 *.В своей проге я учитываю только приоритет считанного символа и лежащего в вершине стека.Думаю это 1 из причин неправильной работы.
Автор: volvo 24.04.2008 23:11
Цитата
Те если в стеке лежит ** и мы считываем из строки + то из стека достаем ** и стек будет выглядить так + ?
Именно так, если текущий знак - "+", то пока в вершине стека лежит знак операции с бОльшим чем у "+" приоритетом надо вытаскивать значение из вершины, и заносить в строку (и тебе не надо знать, два умножения у тебя или десять занесено в стек, операция производится пока вершина стека содержит то, что тебя устраивает).
Автор: blackhard 24.04.2008 23:19
Цитата(volvo @ 25.04.2008 0:11)
Именно так, если текущий знак - "+", то пока в вершине стека лежит знак операции с бОльшим чем у "+" приоритетом надо вытаскивать значение из вершины, и заносить в строку (и тебе не надо знать, два умножения у тебя или десять занесено в стек, операция производится пока вершина стека содержит то, что тебя устраивает).
Все спасибо теперь я знаю в чем точно ошибка (надеюсь единственная) я запоминал ранг операции которую заносил в стек, а ведь насамом деле надо просто посмотреть че лежит сверху без выталкивания.
Автор: blackhard 29.04.2008 18: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
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; } }
Рабочий алгоритм перевода из инфиксной формы в постфиксную
С каких пор программа, не проходящая компиляцию (GCC), является "рабочей", можно уточнить?
Автор: blackhard 1.05.2008 0: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() {
Добавлено через 9 мин. А вот если у меня выражение будет содержать не просто буквы a...Z или цифры 1..9 а имена переменных т.е (Ax1+num)*c-Chis.Как в таком случае реализовать перевод?Нужно будет сделать 2 стека 1для строк 2й для знаков +.-...? Как формировать элементы для помещения в стек строк(т.е как выдирать Ax1 эти переменные и когда их в стек пихать )?
Автор: volvo 1.05.2008 2:28
Цитата
А вот если у меня выражение будет содержать не просто буквы a...Z или цифры 1..9 а имена переменных
По ссылке, которую я тебе давал, есть алгоритм перевода, в котором написано:
Цитата
Выpажение сканиpyется слева напpаво, пpи этом pазбиваясь на токены - числа и знаки аpифметических опеpаций.
Если очеpедной токен - число, не глядя пишем его в выходнyю стpокy.
Так что записывать имена переменных в стек вообще не надо... А вот как выдирать из входной строки эти имена - это подумай... В конце концов, имя переменной не может содержать в себе знаки операций и скобки (это можно считать подсказкой).
Автор: blackhard 1.05.2008 10:32
Блин чето запутался.Если у меня массив строк и указатель на него
*Stack2[Len],**ST2=Stack2
Как мне в 1строку этого массива спомощью указателя записать символы?
Автор: volvo 1.05.2008 11:03
Ну, пока у тебя не массив строк, а массив указателей на строки. Под сами строки еще надо выделить память...