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ố 15 kết quả

Đề tài: Chuyển Trung tố sang hậu tố trong C

  1. #1
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Post Chuyển Trung tố sang hậu tố trong C

    Mình có làm qua cái này rồi, có 2 cách làm: dùng mảng hoặc dùng node và làm theo cấu trúc stack.

    Biểu thức trung tố: 2*(3+4)
    Biểu thức hậu tố: 234+*
    Nói sơ sơ thì biểu thức hậu tố là biểu thức mà các toán tử được đặt ở phía sau 2 toán hạng thay vì đặt ở giữa 2 toán hạng.

    Sau đây là code:
    C++ Code:
    1. #include <iostream>
    2. #include <string>
    3. #define maxx 255
    4. using namespace std;
    5. struct anode{
    6.        char ope; int val;
    7. };
    8. struct node{
    9.        char ope; int val;
    10.        node *l,*r;
    11. };
    12. char num[10]={'0','1','2','3','4','5','6','7','8','9'};
    13. char ope[4]={'+' , '-' , '*' , '/'};
    14.  
    15. void read(string&);
    16. void write(anode[],int);
    17. bool isope(char);
    18. bool isnum(char);
    19. int power(int,int);
    20. int ctoi(char[],int);
    21. int prio(char);
    22. void get(string,anode[],int&);
    23.  
    24. int main(){
    25.     string expr; anode suff[maxx]; int n = 0;
    26.     read(expr);
    27.     get(expr,suff,n);
    28.     write(suff,n);
    29.     fflush(stdin); getchar();
    30.     return 0;
    31. }
    32.  
    33. void read(string &expr){
    34.      cout <<"Nhap bieu thuc tinh toan: ";
    35.      cin >>expr;
    36. }
    37. void write(anode suff[],int n){
    38.      cout <<"Chuyen thanh bieu thuc hau to: \n";
    39.      for (int i = 0;i < n;i++)
    40.      if (suff[i].ope != '.') cout <<suff[i].ope <<' ';
    41.      else cout <<suff[i].val <<' ';
    42.      cout <<endl;
    43. }
    44. bool isope(char c){
    45.      int i = 0;
    46.      while ((i < 4)&&(c != ope[i])) ++i;
    47.      if (i < 4) return true;
    48.      else return false;
    49. }
    50. bool isnum(char c){
    51.      int i = 0;
    52.      while ((i < 10)&&(c != num[i])) ++i;
    53.      if (i < 10) return true;
    54.      else return false;
    55. }
    56. int power(int x,int y){
    57.     int p = 1;
    58.     for (int i = 0;i < y;i++) p *= x;
    59.     return p;
    60. }
    61. int ctoi(char c[],int n){
    62.     int m = 0;
    63.     for (int i = 0; i <= n;i++){
    64.         int j = 0;    
    65.         while ((j < 10)&&(c[i] != num[j])) j++;
    66.         m += j*power(10,n-i);
    67.     }
    68.     return m;
    69. }
    70. int prio(char c){
    71.     if (c == '$') return 0;
    72.     else if ((c == '(')||(c == ')')) return 1;
    73.          else if ((c == '+')||(c == '-')) return 2;
    74.               else return 3;
    75. }
    76. void get(string expr,anode suff[],int& n){
    77.      char cnum[5],stack[maxx]; int m,top = 0,i = 0;
    78.      stack[top] = '$';
    79.      while (i < expr.size()){
    80.            if (isope(expr[i]))
    81.               if (prio(expr[i]) > prio(stack[top]))
    82.                  stack[++top] = expr[i++];
    83.               else{
    84.                    while (prio(expr[i]) <= prio(stack[top])){
    85.                          suff[n].val = -1;
    86.                          suff[n++].ope = stack[top--];
    87.                    }
    88.                    stack[++top] = expr[i++];
    89.               }
    90.            if (isnum(expr[i])){
    91.               m = -1;
    92.               while ((i < expr.size())&&(isnum(expr[i])))
    93.                     cnum[++m] = expr[i++];
    94.               m = ctoi(cnum,m);
    95.               suff[n].ope = '.';
    96.               suff[n++].val = m;
    97.            }
    98.            if (expr[i] =='(') stack[++top] = expr[i++];
    99.            if (expr[i] ==')'){
    100.               while (stack[top] != '('){
    101.                     suff[n].val = -1;
    102.                     suff[n++].ope = stack[top--];
    103.               }
    104.               top--;
    105.               i++;
    106.            }
    107.      }
    108.      while (stack[top] != '$'){
    109.            suff[n].val = -1;
    110.            suff[n++].ope = stack[top--];
    111.      }
    112. }

    Đầu tiên là bạn đọc biểu thức = chuỗi, sau đó bạn tính toán độ ưu tiên để chuyển sang biểu thức hậu tố và cuối cùng từ biểu thức hậu tố bạn đọc ngược từ sau ra trước để tính toán. Cái này mà nói thì dễ nhưng viết ra thì dài dòng lắm, bạn đọc code chắc sẽ hiểu.

  2. #2
    Ngày gia nhập
    06 2007
    Bài viết
    8

    Trung tố sang hậu tố với một chữ số thôi thì mình còn làm được , Có ai biết làm sao để xử lí với số có nhiều chữ số không? Giúp mình với...
    ví dụ : (12+34)*56/78

  3. #3
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Trích dẫn Nguyên bản được gửi bởi leeffa Xem bài viết
    Trung tố sang hậu tố với một chữ số thôi thì mình còn làm được , Có ai biết làm sao để xử lí với số có nhiều chữ số không? Giúp mình với...
    ví dụ : (12+34)*56/78
    OK có ngay chỉ với một thủ thuật bé bé thế là ra.
    Lúc đầu tớ cũng không nghĩ ra nhưng cu bạn làm được xem bài nó mà ngửa người "Oái oái thế mà không nghĩ ra"
    C++ Code:
    1. const int max=200;
    2. int ktuutien(char a)
    3. {
    4.     if(a=='-')
    5.     return 0;
    6.     if(a=='+')
    7.     return 0;
    8.    if(a=='*')
    9.     return 1;
    10.    if(a=='/')
    11.     return 1;
    12. }
    13. bool kiemtraso(char a)
    14. {
    15.     if((int(a)>=48&&int(a)<=57)||a=='.')
    16.     return true;
    17.    return false;
    18. }
    19. bool kttoantu(char ch)
    20. {
    21.     if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
    22.     return true;
    23.    return false;
    24. }
    25.  
    26. class stack
    27. {
    28.     char data[max];
    29.     int top;
    30.    public:
    31.     bool isempty()
    32.       {
    33.         return top==-1;
    34.       }
    35.         stack()
    36.       {
    37.             top=-1;
    38.       }
    39.       bool push(const char&a)
    40.       {
    41.         if(top==max)
    42.             return false;
    43.         top++;
    44.         data[top]=a;
    45.          return true;
    46.       }
    47.       bool pop(char&a)
    48.       {
    49.         if(top==-1)
    50.             return false;
    51.          a=data[top];
    52.          top--;
    53.       }
    54.       char get_top()const
    55.       {
    56.         return data[top];
    57.       }
    58.       void print()const
    59.       {
    60.         for(int i=0;i<=top;i++)
    61.             cout<<data[i]<<" ";
    62.       }
    63. };
    64.  
    65. bool toanhang(char a)
    66. {
    67.     if(a>=48&&a<=57)
    68.     return true;
    69.    return false;
    70. }
    71.  
    72. /*********************ham` chuyen tu 1 bieu thuc trung to--->hau to *************/
    73. bool conver(char a[],char b[])
    74. {
    75.     stack k;
    76.    int dem=0;
    77.    for(int i=0;i<strlen(a);i++)
    78.    {
    79.     if(kttoantu(a[i])&&kttoantu(a[i+1]))           ///kiem tra du lieu dau vao`
    80.         return false;
    81.       if((a[i]>=97&&a[i]<=122)||(a[i]>=65&&a[i]<=90))
    82.         return false;
    83.    }
    84.    for(int i=0;i<strlen(a);i++)
    85.    {
    86.     char ch=a[i];
    87.       if(kiemtraso(ch))
    88.       {
    89.         b[dem++]=ch;
    90.          if(kttoantu(a[i+1]))
    91.             b[dem++]=' ';            //dau cach dung de fan biet giua cac so co nhieu` chu so voi nhau
    92.  
    93.       }
    94.       if(ch=='(')
    95.         k.push(ch);
    96.       if(kttoantu(ch))
    97.       {
    98.         if(!k.isempty())
    99.          {
    100.             if((kttoantu(k.get_top()))&&(ktuutien(ch)==ktuutien(k.get_top())||ktuutien(ch)<ktuutien(k.get_top())))                  // cau lenh nay` kiem tra do uu tien giua cac toan tu
    101.             {
    102.                 char m;
    103.                 k.pop(m);
    104.                 b[dem++]=m;
    105.                   k.push(ch);
    106.             }
    107.             else
    108.             {
    109.                 k.push(ch);
    110.             }
    111.          }
    112.          else
    113.             k.push(ch);
    114.       }
    115.         if(ch==')')   // neu fat hien dau ) thi ta pop cho toi khi gap dau '(" thi` dung`
    116.        {
    117.             char d;
    118.             while(1)
    119.             {
    120.                 k.pop(d);
    121.                if(d=='(')
    122.                 break;
    123.                 b[dem++]=d;
    124.             }
    125.          }
    126.    }
    127.  
    128.    // cau lenh nay dung de lay not so toan tu con lai trong stack..................
    129.    while(!k.isempty())
    130.    {
    131.         char m;
    132.       char n;
    133.     k.pop(m);
    134.       b[dem++]=m;
    135.    }
    136.    b[dem]='\0';
    137. }
    138. float doi(char a)
    139. {
    140.     switch(a)
    141.    {
    142.     case '1': return 1;
    143.         case '2': return 2;
    144.     case '3': return 3;
    145.     case '4': return 4;
    146.     case '5': return 5;
    147.       case '6': return 6;
    148.     case '7': return 7;
    149.     case '8': return 8;
    150.     case '9': return 9;
    151.     case '0': return 0;
    152.  }
    153. }
    154.  
    155.  
    156.  
    157. //// ham` bien doi chuoi sang dang so
    158. float biendoi(char a[])
    159. {
    160.     float d=0;
    161.    int n=strlen(a);
    162.    if(strlen(a))
    163.    {
    164.     for(int i=0;i<n;i++)
    165.       {
    166.         if(a[i]=='.')
    167.          {
    168.             int dem=1;
    169.             float bd1=1,bd=0;
    170.  
    171.             for(int j=i+1;j<n;j++)
    172.             {
    173.                 for(int i=0;i<dem;i++)
    174.                 bd1=bd1*10;
    175.                bd=bd+doi(a[j])/bd1;
    176.  
    177.             }
    178.             d=d+bd;
    179.             break;
    180.          }
    181.          else
    182.                 d=d*10+doi(a[i]);
    183.        }
    184.  
    185.        return d;
    186.    }
    187.    return 0;
    188.  
    189. }
    190. float tinhtoan(char pos[])
    191. {
    192.     char ch='\0';
    193.    stack a;
    194.    int dem1=0;
    195.    float data[1000];
    196.    int n=strlen(pos);
    197.     for(int i=0;i<n;)
    198.    {
    199.     char b[100];
    200.       int dem=0;
    201.     while(pos[i]!=' '&&i<n&&!kttoantu(pos[i]))
    202.       {
    203.         b[dem++]=pos[i++];
    204.       }
    205.       if(dem)
    206.       {
    207.         b[dem]='\0';
    208.         data[dem1++]=biendoi(b);
    209.       }
    210.       if(kttoantu(pos[i]))
    211.       {            
    212.             a.push(ch);
    213.                        
    214.          switch(pos[i])
    215.          {
    216.             case '+':
    217.             {
    218.                 float temp=data[dem1-1]+data[dem1-2];
    219.                     data[dem1-2]=temp;
    220.                      dem1--;
    221.             }break;
    222.             case '-':
    223.             {
    224.                 float temp=data[dem1-2]-data[dem1-1];
    225.                     data[dem1-2]=temp;
    226.                      dem1--;
    227.             }break;
    228.             case '*':
    229.             {
    230.                 float temp=data[dem1-1]*data[dem1-2];
    231.                     data[dem1-2]=temp;
    232.                      dem1--;
    233.             }
    234.             break;
    235.             case '/':
    236.             {
    237.                 float temp=data[dem1-2]/data[dem1-1];
    238.                     data[dem1-2]=temp;
    239.                      dem1--;
    240.             }break;
    241.          }
    242.  
    243.       }
    244.    i++;
    245.    }
    246.   return data[0];
    247. }
    Đã được chỉnh sửa lần cuối bởi iamvtn : 13-11-2007 lúc 11:24 AM.

  4. #4
    Ngày gia nhập
    11 2007
    Nơi ở
    Trái đất
    Bài viết
    7

    Theo tôi, cái việc trung tố hậu tố nghe chừng vất vả quá, thế này nhé, kết quả cuối cùng của biểu thức đó là 1 kết quả ( Giá trị) vậy thì tại sao ta không dựa vào đó, phân tích biểu thức thành vài bước như sau:
    1. Loại bỏ dấu ngoặc -> Khi đó biểu thức của ta chỉ là biểu thức đơn thuần không có dấu ngoặc.
    2. Thực hiện các phép toán nhân và chia -> Biểu thức chỉ còn lại các phép tính cộng trừ.
    3. Thực hiện các phép toán cộng, trừ. -> ra kết quả cuối cùng:
    Thế này nhé
    Sau khi đã xây dựng các hàm trên, ta chỉ việc gọi hàm loại bỏ dấu ngoặc. trong hàm đó gọi hàm loại bỏ dấu nhân chia, sau đó gọi hàm loại bỏ dấu cộng trừ - >Kết quả.
    Không có việc gì khó
    Chỉ sợ tiền không nhiều
    Đào núi và lấp biển
    Không làm được thì đi thuê.

  5. #5
    Ngày gia nhập
    10 2007
    Bài viết
    21

    Trích dẫn Nguyên bản được gửi bởi KimDaiHiep Xem bài viết
    Theo tôi, cái việc trung tố hậu tố nghe chừng vất vả quá, thế này nhé, kết quả cuối cùng của biểu thức đó là 1 kết quả ( Giá trị) vậy thì tại sao ta không dựa vào đó, phân tích biểu thức thành vài bước như sau:
    1. Loại bỏ dấu ngoặc -> Khi đó biểu thức của ta chỉ là biểu thức đơn thuần không có dấu ngoặc.
    2. Thực hiện các phép toán nhân và chia -> Biểu thức chỉ còn lại các phép tính cộng trừ.
    3. Thực hiện các phép toán cộng, trừ. -> ra kết quả cuối cùng:
    Thế này nhé
    Sau khi đã xây dựng các hàm trên, ta chỉ việc gọi hàm loại bỏ dấu ngoặc. trong hàm đó gọi hàm loại bỏ dấu nhân chia, sau đó gọi hàm loại bỏ dấu cộng trừ - >Kết quả.
    Cậu nói thì có vẻ dễ nhỉ, thử thực hiện những lời cậu nói xem, vậy cậu thử up code theo cái mà cậu cho là thế này nhé xem có dễ hơn những bài trên của các bạn không.
    Nói thì phải đi đôi với thực hiện cậu ạ.
    Đã được chỉnh sửa lần cuối bởi Đoàn Dự : 18-11-2007 lúc 01:05 AM.

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    Mặc định Chuyển Trung tố sang hậu tố trong C

    . Loại bỏ dấu ngoặc -> Khi đó biểu thức của ta chỉ là biểu thức đơn thuần không có dấu ngoặc.
    Sai ngay từ câu này ! Sau khi loại bỏ dấu ngoặc thì tính toán biểu thức sẽ sai!
    Đã được chỉnh sửa lần cuối bởi nhc1987 : 18-11-2007 lúc 01:38 AM.
    Keep moving forward!

    ... Retired ...

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

    Theo mình có thể tính toán được biểu thức trung tố mà không cần tới ký pháp ba lan.Tất nhiên việc này không tối ưu bằng giải thuật mà người ta đã nghiên cứu từ lâu nhưng mà việc thực hiện có thể được và giải thuật không quá phức tạp.

    -Trước hết ta xây dựng 1 hàm tính toán các biểu thức +-*/!^ khi không có dấu ngoặc.việc này hoàn toàn thực hiện được.
    -tiếp theo xác định vị trí cặp dấu đóng ngoặc đầu tiêndấu mở ngoặc ngay trước nó.chẳng hạn là i và j ,khi đó ta chỉ cần gọi hàm ở bước trên cho xâu từ i+1 đến j-1.
    -Bước 2 thực hiện xong cho ta xâu kết quả.Nối xâu này vào từ vị trí i đến j đã xác định lúc nãy.Khi đó ta sẽ có 1 xâu tương đương với xâu đầu vào của bước 1.
    gọi lại hàm thực hiện xâu này lại bước 1 cho đến khi hết phép tính và dấu ngoặc thì ta có kết quả.

    ví dụ:
    ta có xâu nhập vào:
    29*(100+19*88)+(25+4)*88
    chú ý vị trí xâu tính từ 0
    -bước 1: vị trí đóng ngoặc đầu tiên và mở ngoặc ngay trước nó là 3 và 14
    giọi hàm tính biểu thức 100+19*88 kết quả là 1772.
    -bước 2: nối vào biểu thức ban đầu ta có 29*1772+(25+4)*88
    -cuối cùng gọi hàm tính lại biểu thức này từ bước 1 khi không còn phép tính và dấu ngoặc thì ta có kết quả.

  8. #8
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Nhc nói đúng đấy iamvtn ít chú ý việc này quá, cố gắng khắc phục nhé.

    về cái việc này tớ lại thích xử lí theo cách này. Trong biểu thức chuyển sang hậu tố với các dữ liệu số lớn thì chúng sẽ được cách nhau bởi dấu '.'

    Có nghĩa là:
    Thay vì:
    ( 1+2) *3 = 123*+
    Thì sẽ là: 1.2.3*+
    Nếu ta qui ước rõ thì khi đọc vào để xử lí biểu thức hậu tố ta sẽ dễ dàng xử lí số lớn hơn.
    Ví dụ trên:
    (12+34)*56/78
    sẽ là 12.34.56.78/*+

    Ý tưởng này là của tớ đấy nhé. He he Nhưng chắc đã bị ngươi ta nghĩ ra mất rồi.

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

    Về số lớn mình có 1 cách giải quyết đó là đưa biểu thức hậu tố vào mảng các xâu.Như thế thì rất dễ xử lý tính toán.

    ví dụ ta có:
    11111+22222*33333+44444/55555
    khi xử lý ta đưa vào mảng các xâu :
    a[0]="11111"
    a[1]="22222"
    a[3]="33333"
    a[4]="*"
    a[5]="+"
    a[6]="44444"
    a[7]="55555"
    a[8]="/"
    a[9]="+"

  10. #10
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Hix tớ chỉ đọc có trang 1 nên ko biết anh em thảo luận nhiều thế rồi ....

    cách của hoangf đã được đề cập đến lâu rồi nhưng vẫn trên mức ý tưởng thôi. Mặt dù là khả thi cho việc code nhưng độ phức tạp rất lớn

    ví dụ:
    ta có xâu nhập vào:
    29*(100+19*88)+(25+4)*88
    chú ý vị trí xâu tính từ 0
    -bước 1: vị trí đóng ngoặc đầu tiên và mở ngoặc ngay trước nó là 3 và 14
    giọi hàm tính biểu thức 100+19*88 kết quả là 1772.
    -bước 2: nối vào biểu thức ban đầu ta có 29*1772+(25+4)*88
    -cuối cùng gọi hàm tính lại biểu thức này từ bước 1 khi không còn phép tính và dấu ngoặc thì ta có kết quả.
    Trước hết cậu phải kiểm tra đk các dấu ngoặc được viết đúng.
    Thứ 2 nữa cậu phải vất vả với các thao tác nối chuỗi nếu biểu thức có nhiều dấu ngoặc:
    vd: 3+8(3+6) + 5*3(2+1) + ... () () () ()

    và điều đặc biệt cậu sẽ phải suy nghĩ đến trường hợp này:

    Đề của cậu:
    29*(100+19*88)+(25+4)*88
    G/S tất cả các hàm của cậu đã đáp ứng, gs đk vào thảo mãn:

    Lần 1: 29*A+(25+4)*88 với A = (100+19*88)
    Lần 2: 29*A+ B*88 với B = (25+4)

    Thế rồi làm sao để cậu giải quyết dấu * đây.
    Đừng nói là Cậu sẽ tiếp tục giải quyết các dấu * này theo kiểu tương tự dấu ngoặc

    Tức
    Lần 3: C+ B*88 với C=29*A
    lần 4: C+ D với D= B*88

    Vẫn ok. Nhưng nếu :
    3*2*5/6 thì lại phức tạp hơn 1 chút.

    BT Hậu Tố là 1 cách giải quyết hay cho vấn đề này.

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

  1. Chuyển đổi trung cấp nghề sang trung cấp chính quy 2012
    Gửi bởi cafetrungnguyen trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 16-07-2012, 04:24 PM
  2. Chuyển trung tố sang hậu tố trong C++ sử dụng ký pháp Balan
    Gửi bởi huynguyen trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 11-06-2012, 03:06 AM
  3. Bị lỗi biên dịch khi sử dụng stack trong việc chuyển trung tố sang hậu tố
    Gửi bởi kuhoang0512 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 16
    Bài viết cuối: 05-11-2011, 01:17 AM
  4. Bài tập C Kỹ thuật Debug với DevC++ trong bài toán chuyển Trung tố sang Hậu tố
    Gửi bởi hienclubvn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 20-09-2010, 10:26 PM
  5. Chuyển trung tố sang hậu tố trong C# như thế nào?
    Gửi bởi hoaxuyenchi trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 10-09-2010, 08:30 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