![]() |
![]() | #1 |
Moderator Join Date: 09 2001 Location: South Korea, Gumi
Posts: 7,699
Blog Entries: 16 Downloads: 102 Uploads: 34
Reputation: 561 | 6 | ![]()
(Alexey Olkhovsky [email protected]) Использyется для вычисления аpифметических выpажений. Для пеpевода в нее необходим стек аpифметических опеpаций. Алгоpитм пеpевода пpоизвольного выpажения в ОПН очень пpост: Выpажение сканиpyется слева напpаво, пpи этом pазбиваясь на токены - числа и знаки аpифметических опеpаций. Если очеpедной токен - число, не глядя пишем его в выходнyю стpокy. Иначе, выталкиваем из стека и пишем в выходнyю стpокy все опеpации с пpиоpитетом выше текyщей, а самy опеpацию пихаем в стек. Левая скобка всегда пишется в стек (ее пpиоpитет - самый низкий). Пpавая скобка выталкивает из стека все опеpации вплоть до левой скобки включительно, сама она в стек не пишется. Когда достигнyт конец входного выpажения, пpосто выталкиваем из стека все что в нем есть. Пpимеp: (2+3)*4+5 левая скобка - пихаем в стек 2 - пишем в выходнyю стpокy + - стек пyст, поэтомy ничего не достаем, а напpотив, пихаем плюс 3 - пишем в выходнyю стpокy пpавая скобка - выталкиваем плюс и левyю скобкy * - стек снова пyст, пихаем yмножение 4 - пишем в выходнyю стpокy + - пpиоpитет yмножения - выше, поэтомy его достаем, а плюс - пихаем 5 - пишем в выходнyю стpокy EOF - достаем из стека плюс Имеем: 2 3 + 4 * 5 + Обpати внимание на следyющее: - Вместо записи в выходнyю стpокy можно тyт же вычислять выpажение, для этого необходим еще один стек (почемy - сообpази сам) - Если выталкивать из стека опеpации с пpиоpитетом выше или pавным текyщемy, то выполнение опеpаций с одинаковым пpиоpитетом бyдет пpоизводиться слева напpаво, т.е. как все мы пpивыкли, да и его глyбина yменьшиться (хоть это и не кpитично) - Скобки в выходнyю стpокy не пишyтся, так как их пpиоpитет yчитывается автоматически; однако их баланс легко пpовеpяется. |
![]() |
![]() | #2 |
Главный инспектор снов Join Date: 01 2002 Location: Yerevan, Armenia
Posts: 329
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Eto nazywaetsja preobrazowanie infixnoj stroki w postfixnuju formu. Podrobnosti na http://freenet.am/~id Tam nashi lekcii po structuram dannyx s primerami na armjanskom jazyke.
|
![]() |
![]() | #3 |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
vot vam source na cpp. Code: /* ----------------------------------------------------------------------------- Infix,postfix and prefix expressions. (c) 2002 Artashes Aghajanyan. Last modified : Fri Jan 18 21:39:46 2002 Yerevan State University, Department of Applied Mathematics. _____________________________________________________________________________ */ #include <iostream.h> /*+++++++++++++++++++++++++++++++++++++++++++++++++++++ stack implementation */ struct node { // stack node int info; node *next; }; class stack { node *ptr; // points to the stack public: stack(); // constructor int is_empty(); // boolean void push(int); int pop(); void dump(); // print stack contents void empty(); // clean the stack }; stack::stack(){ // constructor ptr=NULL; } void stack::push(int a){ node *p; p=new node; p->info=a; p->next=ptr; ptr=p; }; int stack::pop(){ int t; node *p; t=ptr->info; p=ptr; ptr=ptr->next; delete p; return t; }; int stack::is_empty(){ return (ptr==NULL)?1:0; }; void stack::empty(){ while (!is_empty())pop(); }; void stack::dump(){ cout << "dumping the stack\n"; node * p=ptr; while (p!=NULL){ cout << p->info <<' '; p=p->next; }; cout <<'\n'; }; /*+++++++++++++++++++++++++++++++++++++++++++++++++ end stack implementation */ /*++++++++++++++++++++++++++++++++++++++++++++++++ expression implementation */ struct e_node { // node for expression int type; char info; }; class expression { // stack s; // temporary stack e_node *x,*y; // x for infix,y for postfix int n,m; // infix,postfix length void make_postfix(); // create postfix expression void make_infix(); int priority(char); // returns operator priority int read_value(char); // reads from standart input public: expression(const char *); // constructor char *postfix(); // returns postfix (string) int calculate(); // returns expression value(int) }; expression::expression(const char * e){ n=strlen(e); x=new e_node[n]; // allocate x and y y=new e_node[n]; for (int i=1;i<=n;i++){ // set x vector x[i].info=e[i-1]; switch (e[i-1]) { case ')': x[i].type=4;break; case '(': x[i].type=3;break; case '+':case '-':case '*':case '/':case '^': x[i].type=2;break; case '0':case '1':case '2':case '3':case '4': case '5':case '6':case '7':case '8':case '9': x[i].type=0;break; default: x[i].type=1; }; // end switch cout << x[i].info << " ("<< x[i].type<<")\n"; }; // end for make_postfix(); }; char * expression::postfix(){ char *c=new char[m]; for(int i=1;i<=m;i++)c[i-1]=y[i].info; c[m]='\0'; return c; }; int expression::priority(char c){ switch (c) { case '-':case '+': return 1; case '*':case '/': return 2; case '^': return 3; }; }; int expression::read_value(char c){ int x; cout << "\nEnter the value of '"<<c<<"' :"; cin >> x; return x; }; int expression::calculate(){ s.empty(); // clean the stack for (int j=1;j<=m;j++){ switch (y[j].type){ case 0:case 1: if (!y[j].type) s.push(int(y[j].info)-int('0')); else s.push(read_value(y[j].info)); break; case 2: s.dump();cout <<"dumped!!\n"; int argm2,argm1,res; argm2=s.pop(); argm1=s.pop(); switch (y[j].info){ case '+': res=argm1+argm2; break; case '-': res=argm1-argm2; break; case '*': res=argm1*argm2; break; case '/': res=argm1/argm2; break; case '^': res=1; for (int l=1;l<=argm2;l++)res*=argm1; break; }; // end switch (y[j].info) s.push(res); break; }; // end switch (y[j].type) }; // end for return s.pop(); }; // end expression::calculate() void expression::make_postfix(){ int j=0; for (int i=1; i<=n;i++){ // H2 switch (x[i].type){ case 0:case 1: // H3 j++;y[j]=x[i]; break; case 2: // H4 while (!s.is_empty()){ int k=s.pop(); if ( (x[k].type==2) && (priority(x[k].info)>=priority(x[i].info)) ){ j++;y[j]=x[k]; } // end if else { s.push(k); break; // break from while }; // end else }; // end while s.push(i); break; case 3: // H5 s.push(i); break; case 4: // H6 int k=s.pop(); while (x[k].type!=3){ j++; y[j]=x[k]; k=s.pop(); }; break; }; // end switch }; // end for while (!s.is_empty()){ // H7 stack cleanup int k=s.pop(); j++; y[j]=x[k]; }; m=j; }; /*++++++++++++++++++++++++++++++++++++++++++++ end expression implementation */ void main() { int i=0; stack st; //for (i=0;i<100;i++)st.push(i); //st.dump(); expression e("(a-b)*2^(c+1)"); cout << e.postfix()<<"\n"; cout << e.calculate()<<"\n"; } |
![]() |
![]() | #4 |
Дошкольник Join Date: 02 2002 Location: found. AT labs.
Posts: 69
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Artash, loool pomnish' ty poslal mne?? ya modificiroval ETO do tex por poka ne ponyal chto nado polnostyu perepisyvat'... leksicheskiy analiztor trudno vpixivat' + produkctions are hardcoded... kstati, vse-taki kompiliruetsya, i vse to je delaet.. ![]() esli xochesh' mogu obratno poslat' |
![]() |
![]() | #5 |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Да, хочу ![]() Насчет hardcoded согласен. Дело в том что алгоритм мы сами не придумывали. Нам просто был задан алгоритм ( в комментах - H1-H6 ), и мы должны были написать имплементацию на C++. А что такое лексический/синтаксический анализ, я узнал только в этом семестре ![]() |
![]() |
Sponsored Links |
![]() |
Thread Tools | |
|
На правах рекламы: | |
![]() | |