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

Đề tài: Lập trình C++ | Nâng cao bài toán Ký pháp nghịc đảo Ba Lan?

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

    Mặc định Lập trình C++ | Nâng cao bài toán Ký pháp nghịc đảo Ba Lan?

    Mình đã viết được code của bài toán "chuyền biểu thức toán học dạng trung tố sang hậu tố và tính kết quả của nó" . Nhưng mình cần thêm vài chi tiết nữa.
    _Ví dụ như biểu thức: 5+((1+2)*4)+x
    sẽ cho ra kết quả là 17+x.
    và nếu nhập vào biểu thức có dấu "(", ")" ko hợp lý vd: 5+((1+2)*4+x thì sẽ báo lỗi.
    Mong được sự giúp đỡ của các bạn!!
    Thanks!!

    Code:
    //CHUONG TRINH CHUYEN BIEU THUC TRUNG TO THANH HAU TO & TINH KET QUA BIEU THUC HAU TO
    # include <iostream>
    # include <conio.h>
    # include <string.h>
    using namespace std;
            // Bien toan cuc
            const int SIZE=100;
            char chuoi_trungto[SIZE]={'5','+','(','(','1','+','2',')','*','4',')','+','3'};
            char chuoi_hauto[SIZE]="";
            char *p=chuoi_hauto;
            //Lop stack
            class stack
            {
                    //Thuoc tinh
                    char stack_data[SIZE];
                    int stack_ptr;
                    int stack_size;
                    //Phuong thuc
                    public:
                        //Khoi tao co tham so
                        stack(int);
                        //Khoi tao khong tham so
                        stack();
                        
                        //Ham push du lieu char
                        int        push(char);
                        //Ham push du lieu int
                        int        push(int);
                        //Ham pop du lieu char
                        int        pop(char *);
                        //Ham pop du lieu int
                        int        pop(int *);
                        //Ham xuly
                        void xuly();
                        void xuly(char,int);
    
                        
                        
            };
                
            
            //Khoi tao
            stack::stack(int size)
            {
                    stack_ptr=-1;
                    stack_size=size;
                    
            }
    
    
    
            stack::stack()
            {
                    stack_ptr=-1;
                    stack_size=SIZE;
                    
    
            }
            //Ham push
            int stack::push (char data)
            {
                
                if (stack_ptr>=(stack_size-1))
                {
                    return 0;
                }
                else
                {
                    stack_data[++stack_ptr]=data;
                    return 1;
                }
            }
    
            int stack::push (int data)
            {
                
                if (stack_ptr>=(stack_size-1))
                {
                    return 0;
                }
                else
                {
                        stack_data[++stack_ptr]=data;
                        return 1;
                }
            }
            //Ham pop
            int stack::pop(char *data)
            {
                if (stack_ptr==-1)    
                {
                    return 0;
                }
                else
                {
                    *data=stack_data[stack_ptr--];
                    return 1;
                }
            }
    
            int stack::pop(int *data)
            {
                if (stack_ptr==-1)    
                {
                    return 0;
                }
                else
                {
                    *data=stack_data[stack_ptr--];
                    return 1;
                }
            }
            //Ham xu ly
            void stack::xuly()
            {
                char ch2;
                while (pop(&ch2))
                {
                    if (ch2=='(')
                        break;
                    else
                        *p++=ch2;
                
                }
            }
    
            void stack::xuly(char ch, int ut1)
            {
                int ut2;
                char ch2;
                while (pop(&ch2))
                {
                    if (ch2=='(')
                    {
                        push(ch2);
                        break;
                    }
                    else
                    {
                        if ((ch2=='+')||(ch2=='-'))
                            ut2=1;
                        else
                            ut2=2;
                        if (ut2<ut1)
                        {
                            push(ch2);
                            break;
                        }
                        else
                        {
                            *p++=ch2;
                            break;
                        }        
                    }
                }
                push(ch);    
            }
    
    
    //Ham chinh
    int main()
    {    
        char ch;
        int index;
        
        //Qua trinh chuyen trung to sang hau to
        
        int len_trungto=(int)strlen(chuoi_trungto);
        stack pst(len_trungto-1);    
        for (index=0;index<len_trungto;index++)
        {
            ch=chuoi_trungto[index];
            switch (ch)
            {
                case '+' :
                case '-' :
                    pst.xuly(ch,1);
                    break;
                case '*' :
                case '/' :
                    pst.xuly(ch,2);
                    break;
                case '(' :
                    pst.push(ch);
                    break;
                case ')' :
                    pst.xuly();
                    break;
                default :
                    *p++=ch;
            }
        }
        while(pst.pop(&ch))
        {
            *p++=ch;
        }
    
        //Qua trinh tinh gia tri cua chuoi hau to
        int number1,number2,kq;
        int len_hauto=(int)strlen(chuoi_hauto);
        stack result(len_hauto);
        for (index=0;index<len_hauto;index++)
        {
            ch=chuoi_hauto[index];
            switch (ch)
            {
                case '0' :            
                case '1' :
                case '2' :            
                case '3' :
                case '4' :
                case '5' :            
                case '6' :            
                case '7' :
                case '8' :        
                case '9' :
                    
                    result.push((int)(ch-'0'));
                    break;
                    
                case '+' :
                    result.pop(&number1);        
                    result.pop(&number2);                
                    result.push(number1+number2);
                    break;
                    
                case '-' :
                    result.pop(&number1);        
                    result.pop(&number2);                
                    result.push(number1-number2);
                    break;
                    
                case '*' :
                    result.pop(&number1);        
                    result.pop(&number2);                
                    result.push(number1*number2);
                    break;    
    
                case '/' :
                    result.pop(&number1);        
                    result.pop(&number2);                
                    result.push(number1/number2);
                    break;            
                                
            }
        }
        
        result.pop(&kq); 
        cout <<"BIEU THUC TRUNG TO:\n"<<chuoi_trungto <<"\n" ;
        cout <<"BIEU THUC SAU KHI CHUYEN :\n" <<chuoi_hauto <<"\n" ;
        cout <<"GIA TRI CUA BIEU THUC HAU TO=" <<kq <<"\n";
        cout <<"END"<<"\n";
        getch();
        return 0;
    }

  2. #2
    Ngày gia nhập
    02 2009
    Bài viết
    21

    bài bạn tốt quá , còn câu hỏi của bạn tớ cho rằng cứ nhập đúng đủ thôi .

  3. #3
    Ngày gia nhập
    02 2009
    Bài viết
    21

    mà bạn ơi mình chuyển bài bạn yêu cầu nhập chuỗi vào , nhưng nếu chuỗi đó mà có phép trừ cuối cùng thì luôn ra sai , mình cũng không hiểu tại sao sai , bạn kiểm tra lại xem

  4. #4
    Ngày gia nhập
    11 2008
    Bài viết
    21

    Kiểm tra ngoặc thì mình nghĩ chỉ cần đếm số mở ngoặc và đóng ngoặc, nếu thấy trong khi đếm mà đóng nhiều hơn mở là sai, đếm xong mà đóng khác mở thì cũng sai.

    Còn đây là code dùng stack để kiểm tra tính hợp lệ 3 loại ngoặc (), [], {} có xét độ ưu tiên:
    C++ Code:
    1. /*
    2.     Program extracts from Chapter 2 of
    3.     "Data Structures and Program Design in C++"
    4.     by Robert L. Kruse and Alexander J. Ryba
    5.     Copyright (C) 1999 by Prentice-Hall, Inc.  
    6.    
    7.     All rights reserved.
    8. */
    9.  
    10. #include <iostream>
    11. #define SUCCESS true
    12. #define OVERFLOW false
    13. #define UNDERFLOW false
    14. #define Stack_entry char
    15.  
    16. using std::cout;
    17.  
    18. const int maxstack = 10;   //  small value for testing
    19.  
    20. class Stack {
    21. public:
    22.    Stack();
    23.    bool empty() const;
    24.    bool pop();
    25.    bool top(Stack_entry &item) const;
    26.    bool push(const Stack_entry &item);
    27.  
    28. private:
    29.    int count;
    30.    Stack_entry entry[maxstack];
    31. };
    32.  
    33.  
    34. bool Stack::push(const Stack_entry &item)
    35. /*
    36. Pre:  None.
    37. Post: If the Stack is not full, item is added to the top
    38.       of the Stack.  If the Stack is full,
    39.       an bool of overflow is returned and the Stack is left unchanged.
    40. */
    41.  
    42. {
    43.    bool outcome = SUCCESS;
    44.    if (count >= maxstack)
    45.       outcome = OVERFLOW;
    46.    else
    47.       entry[count++] = item;
    48.    return outcome;
    49. }
    50.  
    51.  
    52. bool Stack::pop()
    53. /*
    54. Pre:  None.
    55. Post: If the Stack is not empty, the top of
    56.       the Stack is removed.  If the Stack
    57.       is empty, an bool of underflow is returned.
    58. */
    59.  
    60. {
    61.    bool outcome = SUCCESS;
    62.    if (count == 0)
    63.       outcome = UNDERFLOW;
    64.    else --count;
    65.    return outcome;
    66. }
    67.  
    68.  
    69. bool Stack::top(Stack_entry &item) const
    70. /*
    71. Pre:  None.
    72. Post: If the Stack is not empty, the top of
    73.       the Stack is returned in item.  If the Stack
    74.       is empty an bool of underflow is returned.
    75. */
    76.  
    77. {
    78.    bool outcome = SUCCESS;
    79.    if (count == 0)
    80.       outcome = UNDERFLOW;
    81.    else
    82.       item = entry[count - 1];
    83.    return outcome;
    84. }
    85.  
    86.  
    87. bool Stack::empty() const
    88. /*
    89. Pre:  None.
    90. Post: If the Stack is empty, true is returned.
    91.       Otherwise false is returned.
    92. */
    93.  
    94. {
    95.    bool outcome = true;
    96.    if (count > 0) outcome = false;
    97.    return outcome;
    98. }
    99.  
    100.  
    101. Stack::Stack()
    102. /*
    103. Pre:  None.
    104. Post: The stack is initialized to be empty.
    105. */
    106. {
    107.    count = 0;
    108. }
    109.  
    110. int main()
    111. /*
    112.       The program has notified the user of any bracket
    113.       mismatch in the standard input file.
    114. */
    115.  
    116. {
    117.    Stack openings;
    118.    char symbol;
    119.    bool is_matched = true;
    120.  
    121.    while (is_matched && (symbol = cin.get()) != '\n') {
    122.       if (symbol == '{' || symbol == '(' || symbol == '[')
    123.          openings.push(symbol);
    124.       if (symbol == '}' || symbol == ')' || symbol == ']') {
    125.          if (openings.empty()) {
    126.             cout << "Unmatched closing bracket " << symbol
    127.                  << " detected." << endl;
    128.             is_matched = false;
    129.          }
    130.  
    131.          else {
    132.             char match;
    133.             openings.top(match);
    134.             openings.pop();
    135.             is_matched = (symbol == '}' && match == '{')
    136.                          || (symbol == ')' && match == '(')
    137.                          || (symbol == ']' && match == '[');
    138.             if (!is_matched)
    139.                cout << "Bad match " << match << symbol << endl;
    140.          }
    141.       }
    142.    }
    143.    if (!openings.empty())
    144.       cout << "Unmatched opening bracket(s) detected." << endl;
    145. }
    Đã được chỉnh sửa lần cuối bởi regist : 06-05-2009 lúc 10:41 PM.

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

    @khoathu
    PHP Code:
    int stack::push (char data)
            {
                
                if (
    stack_ptr>=(stack_size-1))
                {
                    return 
    0;
                }
                else
                {
                    
    stack_data[++stack_ptr]=data;
                    return 
    1;
                }
            }

            
    int stack::push (int data)
            {
                
                if (
    stack_ptr>=(stack_size-1))
                {
                    return 
    0;
                }
                else
                {
                        
    stack_data[++stack_ptr]=data;
                        return 
    1;
                }
            }
            
    //Ham pop
            
    int stack::pop(char *data)
            {
                if (
    stack_ptr==-1)    
                {
                    return 
    0;
                }
                else
                {
                    *
    data=stack_data[stack_ptr--];
                    return 
    1;
                }
            }

            
    int stack::pop(int *data)
            {
                if (
    stack_ptr==-1)    
                {
                    return 
    0;
                }
                else
                {
                    *
    data=stack_data[stack_ptr--];
                    return 
    1;
                }
            }
            
    //Ham xu ly
            
    void stack::xuly()
            {
                
    char ch2;
                while (
    pop(&ch2))
                {
                    if (
    ch2=='(')
                        break;
                    else
                        *
    p++=ch2;
                
                }
            } 
    có return rùi bỏ mấy cái else sau if đi.

  6. #6
    Ngày gia nhập
    02 2009
    Bài viết
    21

    Mặc định Lập trình C++ | Nâng cao bài toán Ký pháp nghịc đảo Ba Lan?

    mà bạn khoathu ơi mình chạy thử chương trình nhiều lần thì thấy hình như chương trình của bạn chưa cho kêt quả đúng lắm , mấy cái có 1 cặp ngoặc mà đã tính sai rồi

  7. #7
    Ngày gia nhập
    09 2008
    Bài viết
    3

    Mình nghĩ trước khi dùng hàm nghịch đảo balan bạn nên kiểm tra biểu thức dưới dạng chuổi trước để loại các lỗi cú pháp cơ bản. Ví dụ như:
    - Kiểm tra sự bằng nhau của dấu ngoặc đóng và ngoặc mở, nếu tổng số ngoặc đóng khác tông số ngoặc mở thỉ có hai hướng, 1 là bạn báo lổi biểu thức ko hợp lệ, 2 là dùng một thuật toán theo suy nghĩ của bạn để làm cho chúng bằng nhau.
    - Kiểm tra các ký tự không hợp lệ trong biểu thức và loại bỏ chúng ví dụ như dấu phẩy, dấu : ....
    Cơ bản là mình có một bước chuẩn hóa biểu thức trước khi nghịch đảo balan. Bước này tương đối quan trọng, nếu bạn làm tốt có thể áp dụng cho các phép toán lượng giác (sinx, cosx, tg...)
    Một vài điều góp ý cùng bạn, chúc bạn thành công.

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

    Bạn ơi. Cái Pre và Post trong cái comment có ý nghĩa gì đấy. Cụ thể là Pre và Post

  9. #9
    Ngày gia nhập
    04 2008
    Nơi ở
    HCMC
    Bài viết
    251

    Pre-condition : Tiều điều kiện
    Post-condition: Hậu điều kiện
    C++ Code:
    1. for(;;){cout<<"Busy"<<endl;}
    2. system("cls");
    Hãy ủng hộ cho quỹ phát triển cộng đồng C Việt
    http://congdongcviet.com/quyphattrien-congdongcviet.cpp

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

  1. Liên thông trung cấp nghề,cao đẳng nghề lên đại học 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: 31-07-2012, 02:03 PM
  2. Trả lời: 0
    Bài viết cuối: 02-08-2011, 03:26 PM
  3. Nhập ký tự đầu tiên của một nghề sẽ xuất ra nghề đó bằng việc sử dụng enum?
    Gửi bởi sasadudu 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: 05-03-2011, 09:25 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