Assembly Polish Notation

[slipkot]

Καλησπέρα σε όλη τη παρέα. Έχω μία εργασία στην assembly για Polish Notation και χρειάζομαι τη βοήθεια σας. Υπάρχει στο πρόγραμμα πχ αυτή η πράξη "(1+5)*(8-(4-1))"(δεν δίνεται απο το χρήστη τίποτα) και πρέπει να μετατραπεί σε "15+841--*" υπολογίζοντας και το αποτέλεσμα. Καμία βοήθεια? Ευχαριστώ

[nilosgr]

Δηλαδη να "μετατρεπεις" το '*' σε '+' και το '+' να "ενωννει" τους αριθμους;

 

EDIT: Κοιαξα στο wikipedia αλλο εννοεις

[slipkot]

Όχι... Το "(1+5)*(8-(4-1))" είναι η ενδοθεματική γραφή (όπως πχ θα την έδινε ο χρήστης) και το "15+841--*" είναι η μεταθεματική γραφή ύστερα από την επεξεργασία μέσω του Polish Notation.

 

edit: Άλλο παράδειγμα...

Αλγεβρική έκφραση: (4 + 2 * 5) / (1 + 3 * 2)

Polish Notation: 4 2 5 * + 1 3 2 * + /

[Timonkaipumpa]

Για την μετατροπή από μία μορφή παράστασης σε μία άλλη ΠΡΕΠΕΙ να υλοποιήσεις κάποια δομή δεδομένων. Συνήθεις εφαρμογές υλοποιούν στοίβα και ουρά για την μετατροπή. Όπου στην στοίβα τοποθετείς τις πράξεις και τις παρανθέσεις ενώ στις ουρές την είσοδο και την παράσταση που θα υπολογίσεις.

 

Επίσης, και με δέντρα θα μπορούσε να γίνει.

[MeTaXaS4]

με δέντρα θα ήταν πολύ απλό..

[Bill_cs]

Αυτό είναι η αντίστροφη Πολωνική γραφή.

Το αναφέρουν ως postfix notation.

 

κάνε ένα google search και ίσως βρείς κάτι...

 

αα και γίνεται με στοίβα η υλοποίηση της συνήθως

[Timonkaipumpa]

Και οι τρεις γραφές, προ, μετά και ενδό, μπορούν να υλοποιηθούν με "λίστες" (είτε απλές, δλδ ουρές - στοίβες κτλ, είτε πιο σύνθετες, δέντρα κτλ).

 

Ο πιο εύκολος τρόπος να πάρεις την τελική παράσταση είναι τα δέντρα. Ο πιο εύκολος τρόπος να υλοποιήσεις τις δομές είναι στοίβα (η ουρά χρειάζεται ούτως ή άλλως για την είσοδο).

 

Ας διαλέξει κάτι και ας το κάνει

[V.I.Smirnov]

Καλημέρα.

Το πρόβλημα αυτό είναι αρκετά ενδιαφέρον και εν μέρη έχει ξανασυζητηθεί εδώ στα πλαίσια της C++ (όχι assembly) :

 

http://www.insomnia.gr/topic/393958-%ce%b4%cf%85%ce%b1%ce%b4%ce%b9%ce%ba%ce%b1-%ce%b4%ce%b5%ce%bd%cf%84%cf%81%ce%b1-%ce%ba%ce%b1%ce%b9-%ce%b1%cf%80%ce%bf%cf%81%ce%b9%ce%b5%cf%82/page__p__3778222__hl__reverse+polish+notation__fromsearch__1#entry3778222

 

Πριν πολύ καιρό είχα φτιάξει ένα πρόγραμμα που υπολόγιζε συμβολικά πράξεις και παραγώγους παραστάσεων.

Επιπλέον, το πρόβλημα αυτό λύνεται και με χρήση αναδρομής (έμμεση χρήση του stack).

Έτσι το είχα κάνει στην fortran αλλά εκεί το parser που έφτιαξα έκανε μόνον αριθμητικές πράξεις.

 

Για την προκείμενη περίπτωση, μια απλή λύση είναι η ακόλουθη :

 

>
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <string.h> 
#include <math.h> 

char stack1[50], y; 
float stack2[50], z; 
int top1  = -1, 
   top2  = -1, 
   prec1 =  0,
   prec2 =  0; 

int check(char value) // sets precedence for the operator
{ 
 int prec = 0; 
 
 switch(value) 
 { 
   case '+': 
     prec = 1; 
     break; 

   case '-': 
     prec = 1; 
     break; 

   case '*': 
     prec = 2; 
     break; 

   case '/': 
     prec = 2; 
     break; 

   case '^': 
     prec = 3; 
     break; 

   default : 
     prec = 0; 
 } 
 
 return prec; 
} 

void push1(char x) 
{ 
 top1++; 
 stack1[top1] = x; 
} 

char pop1() 
{ 
 y = stack1[top1]; 
 top1--; 
 return y; 
} 

void push2(float x) 
{ 
 top2++; 
 stack2[top2] = x; 
} 

float pop2() 
{ 
 z = stack2[top2]; 
 top2--; 
 return z; 
} 

void main(void) 
{ 
 char tempa[1], 
      infix[50], 
      postfix[50]; 

 int i = 0,
     j = 0, 
     b = 0,
     n, 
     postfix1[50];

 float af, bf, value; 
 
 
 // reading in the expression
 printf("Enter the expression for evaluating : "); 
 scanf("%s", infix); 
 
 i = strlen(infix); 
 push1('('); 
 infix[i] = ')'; 
 n = i; 
 
 // conversion to postfix 
 for (i = 0; i <= n; i++) 
 { 
   if ((infix[i] >= '0') && (infix[i] <= '9')) 
   { 
     postfix[j] = infix[i]; 
     j++; 
   } 
   else if (infix[i] == '(') 
   { 
     push1(infix[i]); 
     b++; 
   } 
   else if (infix[i] == ')') 
   { 
     b++; 
     while (stack1[top1] != '(') 
     { 
       y = pop1(); 
       postfix[j] = y; 
       j++; 
     } 
     y = pop1(); 
   } 
   else 
   { 
     prec1 = check(infix[i]); 
     prec2 = 4; 
     while (stack1[top1] != '(' && prec2 >= prec1) 
     { 
       prec2 = check(stack1[top1]); 
       if (prec2 >= prec1) 
       { 
         postfix[j] = pop1(); 
         j++; 
       } 
     } 
     push1(infix[i]); 
   } 
 } 
 
 n = n - b + 1; 
 
 printf("\n%s", "The equivalent postfix expression is : "); 
 
 for (i = 0; i < n; i++) 
     printf("%c ", postfix[i]); 
 printf("\n\n"); 
 
 // evaluation of the postfix expression
 for (i = 0; i < n; i++) 
 { 
   tempa[0] = postfix[i]; 
   j = atoi(tempa); 
   postfix1[i] = j; 
 } 
 
 value = 0; 
 top2 = -1; 
 
 for (i = 0; i < n; i++) 
 { 
   if (postfix[i] >= '0' && postfix[i] <= '9') 
     push2(postfix1[i]); 
   else 
   { 
     bf = pop2(); 
     af = pop2(); 

     switch(postfix[i]) 
     { 
       case '+': 
         value = af + bf; 
         break; 

       case '-': 
         value = af - bf; 
         break; 

       case '*': 
         value = af * bf; 
         break; 

       case '/': 
         value = af / bf; 
         break; 

       case '^': 
         value = pow(af, bf); 
         break; 
     } 

     push2(value); 
   } 
 } 
 
 printf("%s %f", "The value is : \n", value); 
 getch(); 
}

 

 

Χάριν απλότητος, το παραπάνω δουλεύει σωστά μόνον με μονοψήφιους αριθμούς.

Π.χ. το 5+3*(2^3/2)-1) δίνει

5 3 2 3 ^ 2 / 1 - * +

και με τιμή 14.

 

-

[slipkot]

Σας ευχαριστώ όλους για τη βοήθεια!