Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Bài tập tính giá trị biểu thức trung tố bằng cây nhị phân!

  1. #1
    Ngày gia nhập
    04 2010
    Bài viết
    69

    Mặc định Bài tập tính giá trị biểu thức trung tố bằng cây nhị phân!

    Em đang làm bài tập về phần tính giá trị biểu thức trung tố bằng cây nhị phân! Em đang thắc mắc không biết là cây nhị phân này sẽ được thể hiện như thế nào(gồm các trường gì)...Em thường thấy là chuyển từ trung tố sang tiền tố hay hậu tố đều làm bằng stack...vậy có thể chuyển chúng bằng cây được không? Hay là chỉ có stack mới làm được! Anh chị có thể giúp cho em về thuật toán được chứ. Nếu được code thì quá tốt! Khi đã có được biểu thức tiền tố...ta phải làm như thế nào để biến nó thành một cây nhị phân! Hic em đọc tài liệu mà ít phần hướng dẫn quá nên củng chưa biết phải bắt đầu từ đâu...mong anh chị giúp cho em phân này vơi!

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    @ kuhoang: Để thực hiện tính toán = cây nhị phân thì bạn hãy đọc tài liệu, người ta có nõi rất rõ. Đọc ngay link của y5k72pk sẽ rất hay.
    Muốn giỏi thì phải đọc thôi, ko còn cách nào khác cả

    Còn về thắc mắc của bạn mình xin đáp như sau:
    Bởi vì cách bố trí của cây nhị phân quá rõ ràng
    Cũng nhờ vào đấy để ta tính toán luôn. Ko nhất thiết phải dùng stack.
    Ví dụ đơn giản : (ko kể đến suy biến nhé)
    if root là toán tử :
    return root->left (toán tử) root->right;
    else (là toán hạng (nút lá) )
    return chính nó;
    Giả sử có cái nhỏ nhỏ : 4 + 5 . Root đang là dấu + . Nó sẽ return ngay 4 (thực hiện + ) với 5 , cho ra kết quả
    Um Mani Padme Hum...!!

  3. #3
    Ngày gia nhập
    04 2010
    Bài viết
    69

    Em vẫn chưa rõ lắm thuật toán chuyển từ trung tố sang tiền tố bằng cây nhị phân! Còn toán tử đổi dấu và toán tử số mũ thì độ ưu tiên của nó có cao hơn các toán tử còn lại không,ta phải xử lý như thế nào!
    Đã được chỉnh sửa lần cuối bởi kuhoang0512 : 27-11-2011 lúc 03:41 PM.

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Cây nhị phân là để tính toán.
    Bạn duyệt cây theo tiền thứ tự thì nó sẽ ra cho bạn tiền tố , duyệt hậu thứ tự thì nó sẽ ra cho bạn hậu tố. Duyệt trung thứ tự thì sẽ ra trung tố (thứ tự thực hiện từ trái qua phải, không cần ngoặc)
    Bạn thực hiện tính trên cây nhị phân thì nó sẽ tính ra cho bạn kết quả.

    Việc của bạn là làm sao giờ nhét cái biểu thức trung tố vào cây cho đúng các vị trí mà thôi.
    Và làm thế nào thì hãy đọc tài liệu Tài liệu hay thế cơ mà
    Rõ ràng bạn ko chịu đọc tài liệu gì cả
    Đã được chỉnh sửa lần cuối bởi clchicken : 27-11-2011 lúc 06:51 PM.
    Um Mani Padme Hum...!!

  5. #5
    Ngày gia nhập
    04 2010
    Bài viết
    69

    Cho em hỏi thêm một điều em đang còn thắc mắc!
    Con trỏ của kiểu dữ liệu này có thể trỏ sang được kiểu dữ liệu khác không!
    VD:
    Em đã tạo một kiểu dữ liệu cây
    C++ Code:
    1. struct ExpNode
    2. {
    3.       int Type;     //0,1,2,3,4,5,6 tương ứng với lá, cộng, trừ, nhân, chia,  %, đổi dấu
    4.       ExpNode *left;
    5.       ExpNode *right;
    6. }

    Khi nếu là lá tức là Type=0;
    Em có thể dùng con trỏ right để trỏ sang kiểu dữ liệu như sau được không
    C++ Code:
    1. struc NodeLeaf
    2. {
    3.        char *Symbol;
    4.        float Value;
    5. }

    Nếu không được thì anh chị có thể gợi ý cho em mình phải tạo dữ liệu một cây như thế nào để phù hợp với bài toán này, bài toán này có thể nhập được các kí tự...
    tức là có thể nhập vào: a+b nhưng khi tính thì bắt buộc phải nhập giá trị cho a và b

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mặc định Bài tập tính giá trị biểu thức trung tố bằng cây nhị phân!

    Bạn cứ thử trỏ một phát rồi truy xuất đến các trường của nó là sẽ hiểu ngay ấy mà
    Mọi thứ trong tầm tay^^
    Um Mani Padme Hum...!!

  7. #7
    Ngày gia nhập
    04 2010
    Bài viết
    69

    ...............
    Bài đã có ở bên dưới
    Đã được chỉnh sửa lần cuối bởi kuhoang0512 : 14-09-2012 lúc 12:35 AM.

  8. #8
    Ngày gia nhập
    04 2010
    Bài viết
    69

    ....................
    Đã được chỉnh sửa lần cuối bởi kuhoang0512 : 14-09-2012 lúc 12:35 AM.

  9. #9
    Ngày gia nhập
    04 2010
    Bài viết
    69

    Mình đã làm được bài tính giá trị biểu thức trung tố bằng cây...tuy còn nhiều sai sót nhưng dù sao mình củng chia sẽ cho mọi người để mọi người tham khảo
    C++ Code:
    1. #include <iostream>
    2. #include <conio.h>
    3. #include <math.h>
    4. #include <ctype.h>
    5. using namespace std;
    6.  
    7. #define MAX 10
    8. #define EMPTY -1
    9.  
    10. struct ExpNode
    11. {
    12.     int Type;    //0,1,2,3,4,5,6
    13.     char *Symbol;  // de luu cac bien ki tu a,b,c,d
    14.     float value;    //de chua gia tri cua bien
    15.     ExpNode *left;
    16.     ExpNode *right;
    17. };
    18.  
    19. struct stack
    20. {
    21.     ExpNode *data[MAX];
    22.     int Top;
    23. };
    24.  
    25. int isempty(stack *s)
    26. {
    27.     return (s->Top == EMPTY)? 1 : 0;
    28. }
    29.  
    30. void emptystack( stack *s )
    31. {
    32.     s->Top = EMPTY;
    33. }
    34.  
    35. //-----------Ham dao chuoi---------------
    36. char *daochuoi (const char *str)
    37. {
    38.     int len = strlen(str);
    39.     char *tam=new char(len+1);
    40.     for( int i=0; i <= len/2; i++ )
    41.     {
    42.         tam[i] = str[len-i-1];
    43.         tam[len-i-1] = str[i];
    44.     }
    45.     tam[len] = 0;
    46.     return tam;
    47. }
    48.  
    49. //-----------Ham push va ham pop---------------
    50. void push(char *S,int &T,char X)
    51. {
    52.     if ( T == 100 )
    53.         cout<<"khong bo sung dc";
    54.     else
    55.         {
    56.             T = T+1;
    57.             S[T] = X;
    58.         }
    59.     return;
    60. }
    61.  
    62.  
    63. void pop( char *S, int &T, char &X )
    64. {
    65.     if ( T == 0 ) return;
    66.     else
    67.         {
    68.             X = S[T];
    69.             T = T-1;
    70.         }
    71.     return;
    72. }
    73.  
    74.  
    75. void push( float *S, int &T, float X)
    76. {
    77.     if ( T == 100 )
    78.         cout<<"khong bo sung dc";
    79.     else
    80.         {
    81.             T = T+1;
    82.             S[T] = X;
    83.         }
    84.     return;
    85. }
    86.  
    87.  
    88.  
    89. void pop( float *S, int &T, float &X )
    90. {
    91.     if ( T == 0 ) cout<<"bieu thuc nhap vao khong dung";
    92.     else
    93.         {
    94.             X = S[T];
    95.             T = T-1;
    96.         }
    97.     return;
    98. }
    99.  
    100.  
    101.  
    102. void push( stack *s, ExpNode *item )
    103. {
    104.     if( s->Top == (MAX-1) )
    105.     {
    106.         cout<<"\n Stack day";
    107.     }
    108.     else
    109.     {
    110.         ++s->Top;
    111.         s->data[s->Top] = item;
    112.     }
    113. }
    114.  
    115.  
    116.  ExpNode* pop( stack *s )
    117.  {
    118.      ExpNode *ret = NULL;
    119.      if( !isempty(s) )
    120.      {
    121.          ret = s->data[s->Top];
    122.          --s->Top;
    123.      }
    124.      return ret;
    125.  }
    126.  
    127.  
    128. //------chuyen chuoi ki tu so thanh so---------
    129. float chuyen( char *a )
    130. {
    131.     int l,flat = -1,dem = 0;
    132.     float s = 0;
    133.     l=strlen(a);
    134.     for ( int i = 0; i < l; i++ )
    135.         if ( a[i] == 46 )       // Neu ky tu bang dau '.'
    136.         {
    137.             flat = i;
    138.             break;
    139.         }
    140.     if ( flat == -1 )
    141.         for ( int i = l-1; i >= 0; i--,dem++ )
    142.             s += ( a[i] - 48 )*pow(double(10),dem);
    143.     else
    144.         {
    145.         for ( int i = flat-1; i >= 0; i--,dem++ )
    146.             s += ( a[i] - 48 )*pow(double(10),dem);
    147.         dem = -1;
    148.         for ( int i = flat+1; i<l; i++,dem-- )
    149.             s += ( a[i] - 48 )*pow(double(10),dem);
    150.         }
    151.     return s;
    152. }
    153.  
    154.  
    155.  
    156.  
    157. //-------------------Do uu tien-----------------
    158. int douutien ( char c )
    159. {
    160.     if( c == '+' || c == '-')
    161.         return 1;
    162.     else if( c == '*' || c == '/' )
    163.         return 2;
    164.     else if( c == '!' )
    165.         return 3;
    166.     else    return 0;
    167. }
    168.  
    169.  
    170. // --------------chuyen tu xau trung to sang xau tien to-----------
    171. char *chuyentrungto ( char *g )
    172. {
    173.     int n = strlen(g),T = 0,j = -1;
    174.     char *h;
    175.     char *inFix;    inFix = daochuoi(g);
    176.     char *chuoihauto = new char[100],x;
    177.     char stack[100];        //luu cac ky tu +,-,*,/,(,)
    178.     char *a=chuoihauto;     //con tro chua chuoi de xuat
    179.    
    180.    
    181.    
    182.         for( int i = 0; i<n; i++ )  // doc chuoi vao: inFix
    183.         {
    184.             if ( inFix[i] != ' ' )
    185.             {
    186.                 if ( ( inFix[i] >= '0' && inFix[i] <= '9' ) || inFix[i] == '.' || inFix[i] >= 'a' && inFix[i] <= 'z' )                  //Neu la toan hang thi cho vao
    187.                 {   a[++j]=inFix[i];                                                //chuoi xuat   
    188.                 if ( ( inFix[i+1] == '+' ) || ( inFix[i+1] == '-' ) || ( inFix[i+1] == '*' ) || ( inFix[i+1] == '/' ) || ( inFix[i+1] == '\0' ) || ( inFix[i+1] == ' ' ) || ( inFix[i+1] == '(' ) )
    189.                         a[++j]=' ';
    190.                 }
    191.                 //Neu gap ki tu ')' thi ta push vao stack
    192.                 else if ( inFix[i] == ')' )
    193.                     push( stack, T, inFix[i] );
    194.                 //Neu gap ki tu '('
    195.                 else if ( inFix[i] == '(' )
    196.                 {
    197.                     while ( stack[T] != ')' )
    198.                     {   pop( stack, T, x ); a[++j] = x; a[++j] = ' ';}
    199.                     //pop phan tu chua ki tu ')' ra khoi stack
    200.                     pop( stack, T, x);
    201.                 }
    202.                 else    //Khi gap cac toan tu(+,-,*,/) ta push vao stack
    203.                 {
    204.                     if ( ( inFix[0] == '-' ) || ( inFix[i] == '-' && inFix[i+1] == '+' ) || ( inFix[i] == '-' && inFix[i+1] == '-' ) || ( inFix[i] == '-' && inFix[i+1] == '*' ) || ( inFix[i] == '-' && inFix [i+1] == '/' )||( inFix [i] == '-' && inFix [i+1] == ')' ) )
    205.                         inFix[i] = '!';
    206.                     while ( ( T != 0 ) && ( douutien( stack[T] ) >= douutien( inFix[i] ) ) )
    207.                     {
    208.                         pop( stack, T, x ); a[++j] = x; a[++j] = ' ';
    209.                     }
    210.                     push( stack, T, inFix[i] );
    211.                 }
    212.             }
    213.            
    214.         }
    215.         //sau khi ra khoi vong for thi Pop het cac phan tu con lai trong stack b vao chuoi xuat
    216.         while( T != 0 )
    217.         {
    218.             pop( stack, T, x ); a[++j] = x; a[++j] = ' ';
    219.         }
    220.         a[j] = '\0';
    221.         h = daochuoi(a);
    222.         //xuat chuoi hau to ra     
    223.         return h;
    224. }
    225.  
    226.  
    227.  
    228. //-------------Tao cay----------
    229. void Taocay( ExpNode **T, char *inFix )
    230. {
    231.     stack X;
    232.     ExpNode *newnode, *op1, *op2;
    233.     char temp[25];  //luu chuoi ki tu so
    234.     char *p , *d;
    235.     float Y;
    236.     int i = 0, j = (strlen(inFix) - 1);
    237.  
    238.     emptystack(&X);
    239.     p = &inFix[strlen(inFix)-1];
    240.    
    241.     while( *p )
    242.     {
    243.         while( *p == ' ' || *p == '\t' || *p == '\0')
    244.         {
    245.             p--; j--;
    246.         }
    247.         if ( isdigit(*p) )
    248.         {
    249.             while( isdigit(*p) )
    250.             {
    251.                 temp[i] = *p;
    252.                 p--; j--;
    253.                 i++;
    254.             }
    255.  
    256.             temp[i]='\0';
    257.             i = 0;
    258.             d = daochuoi(temp);
    259.            
    260.             newnode = new ExpNode;
    261.             Y=chuyen(d);
    262.             newnode->Symbol=new char[strlen(d)];
    263.             strcpy(newnode->Symbol,d);
    264.             newnode->value=Y;
    265.             newnode->Type=0;
    266.             newnode->left = NULL;
    267.             newnode->right = NULL;
    268.             push(&X,newnode);
    269.            
    270.         }
    271.         else if( *p >= 'a' && *p <= 'z')
    272.         {
    273.             newnode = new ExpNode;
    274.             newnode->Symbol=new char[2];
    275.             newnode->Symbol[0] = *p;    newnode->Symbol[1]='\0';
    276.             newnode->Type=0;
    277.             newnode->left = NULL;
    278.             newnode->right = NULL;
    279.             push( &X, newnode );
    280.         }
    281.         else if( *p == '!' )
    282.         {
    283.             op1 = pop(&X);
    284.             newnode = new ExpNode;
    285.             newnode->Type = 6;
    286.             newnode->right = op1;
    287.             newnode->left = NULL;
    288.             push( &X, newnode );
    289.         }
    290.         else
    291.         {
    292.             op1 = pop(&X);
    293.             op2 = pop(&X);
    294.             newnode = new ExpNode;
    295.             if( *p == '+' )
    296.                 newnode->Type = 1;
    297.             else if( *p == '-' )
    298.                 newnode->Type = 2;
    299.             else if( *p == '*' )
    300.                 newnode->Type = 3;
    301.             else if( *p == '/' )
    302.                 newnode->Type = 4;
    303.             else if( *p == '^' )
    304.                 newnode->Type = 5;
    305.            
    306.             newnode->left = op1;
    307.             newnode->right = op2;
    308.             push( &X, newnode );
    309.         }
    310.         if ( j == 0 )
    311.             break;
    312.         p--; j--;
    313.     }
    314.     *T = pop(&X);
    315. }
    316.  
    317.  
    318. void Nhapgiatri( ExpNode *(&T) )
    319. {
    320.     if ( ( T->left == NULL ) && ( T->right == NULL ) )
    321.     {   if ( ( T->Symbol[0] >= 'a' ) && ( T->Symbol[0] <= 'z' ) )
    322.         {
    323.             cout<<"\nNhap gia tri cho bien "<<T->Symbol[0]<<" :";
    324.             cin>>T->value;
    325.         }
    326.     }
    327.     else
    328.     {
    329.         Nhapgiatri(T->left);
    330.         Nhapgiatri(T->right);
    331.     }
    332. }
    333.  
    334.  
    335. float Tinh(ExpNode *T)
    336. {
    337.     switch(T->Type)
    338.     {
    339.     case 0: {
    340.                 return T->value;
    341.             }
    342.     case 1: return Tinh(T->left)+Tinh(T->right); break;
    343.     case 2: return Tinh(T->left)-Tinh(T->right); break;
    344.     case 3: return Tinh(T->left)*Tinh(T->right); break;
    345.     case 4: return Tinh(T->left)/Tinh(T->right); break;
    346.     case 5: return pow(Tinh(T->left),Tinh(T->right)); break;
    347.     case 6: return -Tinh(T->right); break;
    348.  
    349.     }
    350.     return 0;
    351. }
    352.  
    353.  
    354. void main()
    355. {
    356.     char *a, b[100]/**b = "a+1234"*/;
    357.     ExpNode *T;
    358.     a=new char[100];
    359.     float X;
    360.     cout<<"\nnhap chuoi: ";
    361.     gets(b);
    362.     fflush(stdin);
    363.     if(b[0]!='\0')
    364.     {
    365.         a=chuyentrungto(b);
    366.         cout<<"\n chuoi da chuyen sang tien to:"<<a;
    367.         Taocay(&T,a);
    368.         Nhapgiatri(T);
    369.         X=Tinh(T);
    370.         cout<<"\nKet qua tinh duoc la: "<<X;
    371.     }
    372.     else cout<<"\n chuoi rong";
    373.     getch();
    374. }

  10. #10
    Ngày gia nhập
    09 2014
    Bài viết
    2

    Hình như Code của bạn chuyển về tiền tố với số thập phân thì đúng nhưng tính giá trị thì không đúng bạn à.
    vd:
    1.8+2 thì tính ra 9
    1.9+1.2 thì chương trình còn báo lỗi stopped working!

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn