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

[huynguyen]

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:

#include <iostream>#include <string>#define maxx 255using namespace std;struct anode{       char ope; int val;};struct node{       char ope; int val;       node *l,*r;};char num[10]={'0','1','2','3','4','5','6','7','8','9'};char ope[4]={'+' , '-' , '*' , '/'}; void read(string&);void write(anode[],int);bool isope(char);bool isnum(char);int power(int,int);int ctoi(char[],int);int prio(char);void get(string,anode[],int&); int main(){    string expr; anode suff[maxx]; int n = 0;    read(expr);    get(expr,suff,n);    write(suff,n);    fflush(stdin); getchar();    return 0;} void read(string &expr){     cout <<"Nhap bieu thuc tinh toan: ";      cin >>expr;}void write(anode suff[],int n){     cout <<"Chuyen thanh bieu thuc hau to: \n";     for (int i = 0;i < n;i++)      if (suff[i].ope != '.') cout <<suff[i].ope <<' ';     else cout <<suff[i].val <<' ';     cout <<endl;}bool isope(char c){     int i = 0;     while ((i < 4)&&(c != ope[i])) ++i;     if (i < 4) return true;     else return false;}bool isnum(char c){     int i = 0;     while ((i < 10)&&(c != num[i])) ++i;     if (i < 10) return true;     else return false;}int power(int x,int y){    int p = 1;    for (int i = 0;i < y;i++) p *= x;    return p;}int ctoi(char c[],int n){    int m = 0;    for (int i = 0; i <= n;i++){        int j = 0;            while ((j < 10)&&(c[i] != num[j])) j++;        m += j*power(10,n-i);    }    return m;}int prio(char c){    if (c == '$') return 0;    else if ((c == '(')||(c == ')')) return 1;         else if ((c == '+')||(c == '-')) return 2;              else return 3;}void get(string expr,anode suff[],int& n){     char cnum[5],stack[maxx]; int m,top = 0,i = 0;     stack[top] = '$';     while (i < expr.size()){           if (isope(expr[i]))               if (prio(expr[i]) > prio(stack[top]))                  stack[++top] = expr[i++];              else{                   while (prio(expr[i]) <= prio(stack[top])){                         suff[n].val = -1;                         suff[n++].ope = stack[top--];                   }                   stack[++top] = expr[i++];              }           if (isnum(expr[i])){              m = -1;              while ((i < expr.size())&&(isnum(expr[i])))                    cnum[++m] = expr[i++];              m = ctoi(cnum,m);              suff[n].ope = '.';              suff[n++].val = m;           }           if (expr[i] =='(') stack[++top] = expr[i++];           if (expr[i] ==')'){              while (stack[top] != '('){                    suff[n].val = -1;                    suff[n++].ope = stack[top--];              }              top--;              i++;           }     }     while (stack[top] != '$'){           suff[n].val = -1;           suff[n++].ope = stack[top--];     }}

Đầ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.

[leeffa]

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

[iamvtn]

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"

const int max=200;int ktuutien(char a){    if(a=='-')    return 0;    if(a=='+')    return 0;   if(a=='*')    return 1;   if(a=='/')    return 1;}bool kiemtraso(char a){    if((int(a)>=48&&int(a)<=57)||a=='.')    return true;   return false;}bool kttoantu(char ch){    if(ch=='+'||ch=='-'||ch=='*'||ch=='/')    return true;   return false;} class stack{    char data[max];    int top;   public:    bool isempty()      {        return top==-1;      }        stack()      {            top=-1;      }      bool push(const char&a)      {        if(top==max)            return false;        top++;        data[top]=a;         return true;      }      bool pop(char&a)      {        if(top==-1)            return false;         a=data[top];         top--;      }      char get_top()const      {        return data[top];      }      void print()const      {        for(int i=0;i<=top;i++)            cout<<data[i]<<" ";      }}; bool toanhang(char a){    if(a>=48&&a<=57)    return true;   return false;} /*********************ham` chuyen tu 1 bieu thuc trung to--->hau to *************/bool conver(char a[],char b[]){    stack k;   int dem=0;   for(int i=0;i<strlen(a);i++)   {    if(kttoantu(a[i])&&kttoantu(a[i+1]))           ///kiem tra du lieu dau vao`        return false;      if((a[i]>=97&&a[i]<=122)||(a[i]>=65&&a[i]<=90))        return false;   }   for(int i=0;i<strlen(a);i++)   {    char ch=a[i];      if(kiemtraso(ch))      {        b[dem++]=ch;         if(kttoantu(a[i+1]))            b[dem++]=' ';            //dau cach dung de fan biet giua cac so co nhieu` chu so voi nhau       }      if(ch=='(')        k.push(ch);      if(kttoantu(ch))      {        if(!k.isempty())         {            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            {                char m;                k.pop(m);                b[dem++]=m;                  k.push(ch);            }            else            {                k.push(ch);            }         }         else            k.push(ch);      }        if(ch==')')   // neu fat hien dau ) thi ta pop cho toi khi gap dau '(" thi` dung`       {            char d;            while(1)            {                k.pop(d);               if(d=='(')                break;                b[dem++]=d;            }         }   }    // cau lenh nay dung de lay not so toan tu con lai trong stack..................   while(!k.isempty())   {        char m;      char n;    k.pop(m);      b[dem++]=m;   }   b[dem]='\0';}float doi(char a){    switch(a)   {    case '1': return 1;        case '2': return 2;    case '3': return 3;    case '4': return 4;    case '5': return 5;      case '6': return 6;    case '7': return 7;    case '8': return 8;    case '9': return 9;    case '0': return 0; }}   //// ham` bien doi chuoi sang dang sofloat biendoi(char a[]){    float d=0;   int n=strlen(a);   if(strlen(a))   {    for(int i=0;i<n;i++)      {        if(a[i]=='.')         {            int dem=1;            float bd1=1,bd=0;             for(int j=i+1;j<n;j++)            {                for(int i=0;i<dem;i++)                bd1=bd1*10;               bd=bd+doi(a[j])/bd1;             }            d=d+bd;            break;         }         else                d=d*10+doi(a[i]);       }        return d;   }   return 0; }float tinhtoan(char pos[]){    char ch='\0';   stack a;   int dem1=0;   float data[1000];   int n=strlen(pos);    for(int i=0;i<n;)   {    char b[100];      int dem=0;    while(pos[i]!=' '&&i<n&&!kttoantu(pos[i]))      {        b[dem++]=pos[i++];      }      if(dem)      {        b[dem]='\0';        data[dem1++]=biendoi(b);      }      if(kttoantu(pos[i]))      {                         a.push(ch);                                  switch(pos[i])         {            case '+':            {                float temp=data[dem1-1]+data[dem1-2];                    data[dem1-2]=temp;                     dem1--;            }break;            case '-':            {                float temp=data[dem1-2]-data[dem1-1];                    data[dem1-2]=temp;                     dem1--;            }break;            case '*':            {                float temp=data[dem1-1]*data[dem1-2];                    data[dem1-2]=temp;                     dem1--;            }            break;            case '/':            {                float temp=data[dem1-2]/data[dem1-1];                    data[dem1-2]=temp;                     dem1--;            }break;         }       }   i++;   }  return data[0];}

[KimDaiHiep]

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ả.

[Đoàn Dự]

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 ạ.

[nhc1987]

. 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!

[hoang8f]

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ên và dấ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ả.

[kidkid]

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.

[hoang8f]

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]="+"

[kidkid]

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.