|
01.05.2002, 01:07
| #1 |
| Moderator  Join Date: 09 2001 Location: South Korea, Gumi
Posts: 7,699
Blog Entries: 16 Downloads: 102 Uploads: 34
Reputation: 561 | 6 |  Обpатная польская нотация
(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яется. |
 |
|
01.05.2002, 03:32
| #2 |
| Главный инспектор снов  Join Date: 01 2002 Location: Yerevan, Armenia
Posts: 330
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.
|
| |
|
01.05.2002, 11:44
| #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";
} |
| |
|
02.05.2002, 16:22
| #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' |
| |
|
03.05.2002, 11:07
| #5 |
| Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 |
Да, хочу Насчет hardcoded согласен. Дело в том что алгоритм мы сами не придумывали. Нам просто был задан алгоритм ( в комментах - H1-H6 ), и мы должны были написать имплементацию на C++. А что такое лексический/синтаксический анализ, я узнал только в этом семестре  |
| |
| Sponsored Links |
 |
| Thread Tools | |
| |
| На правах рекламы: | |
 | |
