Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Dùng hàm STACK để tính biểu thức hậu tố

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

    Mặc định Dùng hàm STACK để tính biểu thức hậu tố

    Stack thì tớ cũng hiểu 1 chút chứ còn hậu tố thì mù tịt , tuy đã search google những thấy giải thick giài dòng và khó hiểu , bạn nào có thể giúp tớ không .

  2. #2
    Ngày gia nhập
    12 2010
    Bài viết
    33

    Đây là Code của mình viết "đơn sơ nhất có thể"
    File Stack.CPP
    C++ Code:
    1. #ifndef STACK_CPP
    2. #define STACK_CPP 1
    3. template <class T>
    4. class Stack
    5. {
    6.     T *S;
    7.     int N; //so phan tu hien tai cua mang S
    8.     int t; //luu dia chi so cua phan tu duoc dua vao cuoi cung cua stack
    9.     public:
    10.         Stack();
    11.         ~Stack();
    12.         int size();
    13.         int isEmpty();
    14.         T top();          //tra ve phan tu o dinh
    15.         T pop();     //Lay ra mot phan tu o dinh Stack
    16.         void push(T o);    //Them 1 phan tu vao dinh Stack
    17. };
    18. //---------------------------------------------------------------------------
    19. template <class T>
    20. Stack<T>::Stack()
    21. {
    22.     S= new T[1];
    23.     N=1;t=-1;
    24. }
    25. //---------------------------------------------------------------------------
    26. template <class T>
    27. Stack<T>::~Stack()
    28. {
    29.     delete S;
    30. }
    31. //---------------------------------------------------------------------------
    32. template <class T>
    33. int Stack<T>::size()
    34. {
    35.     return t+1;
    36. }
    37. //---------------------------------------------------------------------------
    38. template <class T>
    39. int Stack<T>::isEmpty()
    40. {
    41.     return (t==-1);
    42. }
    43. //-------------------------------------------------------------------------
    44. template <class T>
    45. T Stack<T>::top()
    46. {
    47.     return S[t];
    48. }
    49. //----------------------------------------------------------------------------
    50. template <class T>
    51. T Stack<T>::pop()
    52. {
    53.    T o;
    54.     o=S[t];
    55.     t--;
    56.     return o;
    57. }
    58. //---------------------------------------------------------------------------
    59. template <class T>
    60. void Stack<T>::push(T o)
    61. {
    62.     T *a;
    63.     if (t==N-1)
    64.     {
    65.         N=2*N;  //chien luoc nhan doi
    66.         a=new T[N];
    67.         for (int i=0;i<=t;i++)
    68.             a[i]=S[t];
    69.         delete S;
    70.         S=a;
    71.     }
    72.     t++;
    73.     S[t]=o;
    74. }
    75. #endif

    Ứng dụng Kí pháp Ba Lan
    C++ Code:
    1. #include <iostream.h>
    2. #include <stdlib.h>
    3. #include <string.h>
    4. #include <conio.h>
    5. #include <ctype.h>
    6. #include <STACK.CPP>
    7. //-----------------Ham kiem tra toan tu-------------------------
    8. int isOpr(char c)
    9. {
    10.     if (c=='+' || c=='-' || c=='*' || c=='/')
    11.         return 1;
    12.     return 0;
    13. }
    14. //-------------Ham nhap----------------------------------------
    15. void import(char *c)
    16. {
    17.     cout<<"\nNhap bieu thuc can tinh: ";
    18.     cin.get(c,50);
    19. }
    20. //---------------Check Error-----------------------------------
    21. int checkErr(char *c)
    22. {
    23.     int k=0,l=0;
    24.     for (int i=0;i<=strlen(c);i++)
    25.     {
    26.         if (isOpr(c[i])&&isOpr(c[i+1]))
    27.             return -2;
    28.         if (isalpha(c[i]))
    29.             return  -1;
    30.         if (c[i]=='(' && c[i+1]==')')
    31.             return 1;
    32.         if (c[i]=='(') k++;
    33.         if (c[i]==')') l++;
    34.     }
    35.     if(k>l) return 2;
    36.     else
    37.         if (k<l) return 3;
    38.     return 0;
    39. }
    40. //--------------------Kiem tra tinh uu tien-----------------------
    41. int uutien(char c)
    42. {
    43.     if (isOpr(c))
    44.     {
    45.         if (c=='+'||c=='-') return 1;
    46.         else if (c=='*'||c=='/')    return 2;
    47.     }
    48.    return 0;
    49. }
    50. //--------------Convert Infix to Postfix--------------------------
    51. int convert(char *a, char *b)
    52. {
    53.     switch (checkErr(a))
    54.     {
    55.         case -2:   cout<<"\nLoi nhap: Hai toan tu canh nhau"; return 0;break;
    56.         case -1:   cout<<"\nLoi nhap: Bieu thuc co ky tu la chu";return 0; break;
    57.         case 1:    cout<<"\nLoi nhap: Khong co toan tu trong cap ()";return 0; break;
    58.         case 2:    cout<<"\nLoi nhap: Thieu ngoac )"; return 0;break;
    59.         case 3:       cout<<"\nLoi nhap: Thieu ngoac ("; return 0;break;
    60.     }
    61.     Stack <char>    Opr;
    62.     int d=0;
    63.     for (int i=0;i<strlen(a); i++)
    64.     {   if (a[i]=='(')  Opr.push(a[i]); //neu gap dau ( thi push vao Opr
    65.         else
    66.             if(isdigit(a[i]) || a[i]=='.')    //Neu gap so hoac dau .
    67.             {
    68.                 b[d++]=a[i];    //neu gap so thi luu vao b
    69.                 if (isOpr (a[i+1])) b[d++]=' ';
    70.             }
    71.             else
    72.                 if (isOpr(a[i]))  //neu gap toan tu
    73.                 {
    74.                     if (!Opr.isEmpty())   //neu Stack khong rong
    75.                     {
    76.                         while(uutien(Opr.top()) >= uutien(a[i]))  //kiem tra uu tien
    77.                         {
    78.                             char m;
    79.                             m=Opr.pop();
    80.                             b[d++]=m;
    81.                         }
    82.                         Opr.push(a[i]);
    83.                     }
    84.                     else    Opr.push(a[i]);
    85.                 }
    86.                 else
    87.                     if (a[i]==')')//Neu gap dau )
    88.                     {
    89.                         char n;
    90.                         while (Opr.top()!='(')
    91.                         {
    92.                             n=Opr.pop();
    93.                             b[d++]=n;
    94.                         }
    95.                     n=Opr.pop();
    96.                     }
    97.     }
    98.     while (!Opr.isEmpty())         //khi duyet het cac phan tu ma Stack Opr chua rong
    99.     {
    100.         char p;
    101.         p=Opr.pop();
    102.         b[d++]=p;
    103.     }
    104.     b[d]='\0';
    105.     return 1;
    106. }
    107. //------------------Tinh gia tri bieu thuc dang hau to-------------------
    108. float tinhgtri(char *c)
    109. {
    110.     Stack <float> T;
    111.     for (int i=0;i<=strlen(c);)
    112.     {
    113.         char b[100];
    114.         int k=0;
    115.         if (isdigit(c[i]))
    116.         {
    117.             while (c[i]!=' ' && !isOpr(c[i]))     //Tim so sau do convert -> float
    118.             {
    119.                 b[k]=c[i];
    120.                 k++;i++;
    121.             }
    122.             if (k)  {b[k]='\0';T.push(atof(b));}  // convert tu string sang float
    123.         }
    124.         if (isOpr(c[i])) //gap toan tu thi dinh nghia cho toan tu
    125.         {
    126.             float m=0,n=0;
    127.             switch(c[i])
    128.             {
    129.                 case '+': {m=T.pop();n=T.pop();T.push(m+n);break;}
    130.                 case '-': {m=T.pop();n=T.pop();T.push(n-m);break;}
    131.                 case '*': {m=T.pop();n=T.pop();T.push(m*n);break;}
    132.                 case '/': {m=T.pop();n=T.pop();T.push(n/m);break;}
    133.             }
    134.         }
    135.         i++;
    136.     }
    137.     return T.pop();
    138. }
    139. void main()
    140. {
    141.     clrscr();
    142.     char a[100], b[100];
    143.     float t=0;
    144.     import(a);
    145.     if (convert (a,b))
    146.     {
    147.         cout<<"\nBieu thuc dang hau to: "<<b;
    148.         t=tinhgtri(b);
    149.         cout<<"\nGia tri cua bieu thuc: "<<a<<" = "<<t;
    150.     }
    151.     getch();
    152. }

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

    Trích dẫn Nguyên bản được gửi bởi hoangkianh31592 Xem bài viết
    Đây là Code của mình viết "đơn sơ nhất có thể"
    Bạn có thể nói về ý tưởng thuật toán bài này được không . Cảm ơn !

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

    Trích dẫn Nguyên bản được gửi bởi yuh Xem bài viết
    Bạn có thể nói về ý tưởng thuật toán bài này được không . Cảm ơn !
    Bạn phải dùng từ là : Sử dụng Stack để tính hậu tố chứ ? Chứ hàm stack là cái hàm gì ?

    Ý tưởng :
    Chạy đầu đến cuối chuỗi:
    Gặp operand : "ĐẨY" vào stack .
    Gặp operator: "Móc" Top và Top-1 ra . Thực hiện Top-1 operator Top . Được kết quả bao nhiêu lại ĐẨY vào stack ) .

    Cứ đẩy rồi móc, móc rồi đẩy đến lút vào cuối "con đường" thì thôi

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

    http://my.opera.com/thuynt/blog/ky-p...ich-dao-ba-lan
    Bạn đọc ở đây cho dễ hiểu hơn

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

    Mặc định Dùng hàm STACK để tính biểu thức hậu tố

    Tạo một stack kiểu int (hoặc kiểu dữ liệu phù hợp để tính toán)
    Đọc đến khi hết biểu thức hậu tố.
    • Nếu là toán hạng thì đưa vào stack
    • Nếu là toán tử thì lấy hai phần tử ở đỉnh stack ra rồi tính toán (nên viết hàm tính toán ở ngoài, đồng thời lưu ý thứ tự của toán hạng (VD: ab/ khác ba/, nên nhớ khi đưa vào stack thì thứ tự ab/ sẽ là b,a, do đó hãy lưu ý khi tính toán))
    • Đưa kết quả tính được vào stack.

  7. #7
    Ngày gia nhập
    10 2012
    Bài viết
    1

    Mặc định mọi người giúp e bài tính biểu thức hậu tố này với ạ

    e còn yếu lập trình nên làm hoài mà chả thấy bài nó chạy được
    mọi người sửa giúp e với, cho e biết sai ở đâu ạ

    #include"iostream"
    #include"stdlib.h"
    #include"string.h"
    #include"conio.h"

    #define MAX 100

    using namespace std;
    int stack[MAX];
    int top;

    // stack
    void init(){
    int top = -1;

    }

    void push(int X)
    {
    if(top == MAX-1) cout<<"Stack day"<<endl;
    else { top = top+1;
    stack[top]=X;
    }
    }

    int pop()
    {
    if(top < 0) cout<<"Stack rong"<<endl;
    else { int X;
    X = stack[top];
    top--;
    return X;
    }
    }

    int latoanhang(char a)
    {
    if((a>='0') && (a<='9'))
    return 1;
    else return 0;
    }

    int latoantu(char a)
    {
    if((a=='+') || (a='-') || (a=='*') || (a=='/'))
    return 1;
    else return 0;
    }

    void nhap(char *a)
    {
    cout<<"Nhap bieu thuc can tinh: ";
    cin>>gets(a);
    }
    //tinh hau to
    int tinhhauto(char *a)
    {
    stack[MAX];
    int X1, X2, kq = 0;
    for(int i=0;i<strlen(a);i++)
    {
    if( latoanhang(a[i]))
    {
    int temp= atoi(&a[i]);
    push(temp);
    while (a[i+1] != ' ') i++;
    }
    else if( latoantu(a[i]))
    {
    X1=pop();
    X2=pop();
    if(a[i]=='+') kq=X1+X2;
    if(a[i]=='-') kq=X2-X1;
    if(a[i]=='*') kq=X1*X2;
    if(a[i]=='/') kq=X2/X1;
    push(kq);
    }
    }
    return pop();
    }
    main()
    {
    char a[MAX];
    int t=0;
    nhap(a);
    init();
    t = tinhhauto(a);
    cout<<" Gia tri cua bieu thuc hau to la: "<<t<<endl;
    getch();
    }

  8. #8
    Ngày gia nhập
    03 2012
    Bài viết
    1

    Ban chi can nhap chu "void" vao truoc chu "main" trong ham main la no se chay!
    Nhung theo toi ban da lam sai muc dich cua bai toan tinh hau to.

  9. #9
    Ngày gia nhập
    11 2012
    Bài viết
    9

    THUẬT TOÁN BALAN NGƯỢC(PRN)
    Khi bắt đầu tìm hiểu nó bạn nên tìm hiểu định nghĩa của nó là gì và thử chạy bằng tay. Sau đó search code hoặc tự cài sẽ tốt hơn.

    PRN là biểu thức toán học trong đó toán tử(+ - * / ...) được viết sau toán hạng và không có dấu ngoặc.

    Ví dụ: 2 3 4 + 5 6 - - * là một PRN(Postfix)
    2*((3+4)-(5-6))
    là một infix.


    Thuật toán tính giá trị của PRN:
    1. Khởi tạo Stack rỗng (chứa hằng hoặc biến).
    2. Lặp cho đến khi kết thúc biểu thức:
    Đọc 1 phần tử của biếu thức (hằng, biến, phép toán).
    Nếu phần tử là hằng hay biến: đưa vào Stack.
    Ngược lại:
    Lấy ra 02 phần tử của Stack.
    Áp dụng phép toán cho 02 phần tử vừa lấy ra.
    Đưa kết quả vào Stack.
    3. Giá trị của biểu thức chính là phần tử cuối cùng
    của Stack

    Chạy bằng tay với ví dụ 2 3 4 + 5 6 - - *
    KQ:16
    Đã được chỉnh sửa lần cuối bởi GACN : 15-12-2013 lúc 04:10 PM.

Các đề tài tương tự

  1. bài tập về tính bt hậu tố dùng stack
    Gửi bởi linh_bkan1 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 02-11-2010, 10:14 PM
  2. Dùng Stack kiểm tra số chính phương
    Gửi bởi aydada trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 32
    Bài viết cuối: 20-05-2010, 09:22 PM
  3. Tìm max dùng stack
    Gửi bởi cuongk14 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 18-05-2009, 11:32 PM
  4. Code về stack | Chuyển hệ số 10 sang 2 dùng stack
    Gửi bởi ahappyboy89 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 17-04-2009, 09:48 AM
  5. tính biểu thức hậu tố dùng stack
    Gửi bởi dangx trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 24-03-2009, 09:37 PM

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