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

Đề tài: Vẫn tiếp tục bài "WFF" của môn Logic

  1. #1
    Ngày gia nhập
    09 2008
    Nơi ở
    Hà Đông
    Bài viết
    2

    Wink Vẫn tiếp tục bài "WFF" của môn Logic

    Không bít các Mod có còn nhớ cái bài "WFF" mà đã có người hỏi từ lâu rồi không? Nhưng bây giờ mình cần làm bài này để nộp gấp cho thầy. Trước tiên minh xin nêu lại thuật toán của bài này:

    Code:
    Input: expression Alpha Output: true or false (indicating whether Alpha is a wff ).
    0. Begin with an initial construction tree T containing a single node labeled with Alpha.
    1. If all leaves of T are labeled with propositional symbols, return true.
    2. Select a leaf labeled with an expression Alpha1 which is not a propositional
    symbol.
    3. If Alpha1 does not begin with ( return false.
    4. Examine Alpha1 to find Beta, the first balanced proper initial segment of Alpha1. If there is no such Beta, return false.
    5. If Alpha1=(-Beta), then add a child to the leaf labeled by Alpha1, label it with Beta, and goto 1.
    6. If Alpha1=(Beta & Xichma)where & is one of {^,v,->,<->} and Beta is balanced, then add two children to the leaf labeled by Alpha1, label them with Beta and Xichma, and goto 1.
    7. Return false.
    Bây giờ minh chỉ nghĩ đơn giản thế này thôi:
    Đó là có một chuỗi các ký tự được nhập vào từ bàn phím, sau đó minh đi kiểm tra cái chuỗi ký tự đấy có tuân theo đúng cái "quy tắc" bên trên ko?

    1. Vấn đề đầu tiên mình gặp phải là độ dài của chuỗi ký tự đó ko cố định, nó tùy thuộc vào người nhập vì thế minh định dùng mảng nhưng cũng ko được ổn lắm vì biết dùng mảng kích thước bao nhiêu cho đủ? Còn nếu dung con trỏ thì mình ko biết xin cấp phát thế nào (vì đâu có bít kích thước). Mong các bạn chỉ giúp.

    2. Vấn đề thứ hai là việc tách lấy các chuỗi con của chuỗi ban đầu. Yêu cầu của thuật toán là phải tách lấy chuỗi con Beta cân bằng ngoặc.

    Mong mọi người giúp đỡ !!!
    Đã được chỉnh sửa lần cuối bởi shushu : 18-10-2008 lúc 04:52 PM.

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    1. Vấn đề đầu tiên mình gặp phải là độ dài của chuỗi ký tự đó ko cố định, nó tùy thuộc vào người nhập vì thế minh định dùng mảng nhưng cũng ko được ổn lắm vì biết dùng mảng kích thước bao nhiêu cho đủ? Còn nếu dung con trỏ thì mình ko biết xin cấp phát thế nào (vì đâu có bít kích thước). Mong các bạn chỉ giúp.
    Dùng std::string cho nó grow là ok
    2. Vấn đề thứ hai là việc tách lấy các chuỗi con của chuỗi ban đầu. Yêu cầu của thuật toán là phải tách lấy chuỗi con Beta cân bằng ngoặc.
    std::string C++ có rất nhiều hàm, tách chuỗi là không khó, còn phần check thì cậu dùng stack thử chưa ?
    Tham khảo std::string :
    http://www.cppreference.com/wiki/string/start

  3. #3
    Ngày gia nhập
    09 2008
    Nơi ở
    Hà Đông
    Bài viết
    2

    Uhm! trước hết mình phải nói với bạn là kỹ thuật lập trình của mình còn rất "gà mờ". Vì thế bạn có thể nói rõ hơn ý tưởng của bạn được ko?
    Tất nhiên là cách làm của mình ko làm theo cái thuật toán ở trong sách, vì nó còn yêu cầu xây đựng cây nhị phân rồi sử dụng stack để phá đệ quy... Chính vì trình độ "gà" nên mình chỉ nghĩ là xử lý một chuỗi ký tự thôi. Không xây dựng cây cối j ở đây cả. Mong RR nói rõ hơn :-P
    TÌNH YÊU LÀ VĨNH CỬU
    CHỈ CÓ...NGƯỜI YÊU LÀ THAY ĐỔI

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Đây tui cho cậu 1 ví dụ cắt string, đầu tiên cậu cắt hết các chuỗi khoảng trắng. Lưu vào stack hoặc gì đó thì tùy cậu. Ở đây tui dùng vector< string > để demo cho cậu coi thôi.
    Giải thuật thì cậu phải suy nghĩ trước đã. Cái này cứ dùng stack< string > rồi pop vào đó.
    Sau đó cậu viết ra điều kiện nào theo yêu cầu thì làm gì đó...Cậu làm đi rồi tui sẽ coi. Còn tui làm hết cho cậu thì.... Cái demo tui có viết thêm 1 hàm nhận vào 1 chuỗi dùng std::string C++. Cậu viết C++ thì làm quen với nó đi là vừa. Nếu có thắc mắc chỗ nào thì post lên hỏi, tui sẽ giải thích dòng đó.
    C++ Code:
    1. #include <iostream>
    2. #include <stack>
    3. #include <string>
    4. #include <vector>
    5. #include <algorithm>
    6. #include <iterator>
    7.  
    8. using namespace std;
    9.  
    10. string getLogicString()
    11. {
    12.     string s;
    13.     cout << "Enter a logic string : \n";
    14.     getline( cin, s );
    15.     return s;
    16. }
    17.  
    18. typedef vector< string > vecstr;
    19.  
    20. void cut_string( const string& str, vecstr& vs, const string& delim )
    21. {
    22.     string::size_type b    = 0;
    23.     string::size_type e    = str.find_first_of( delim, b );
    24.     string::size_type slen = str.length();
    25.     string word;
    26.  
    27.     while( string::npos != e && e < slen )
    28.     {
    29.         word = str.substr( b, e - b );
    30.         b    = e + 1;
    31.         e    = str.find_first_of( delim, b );
    32.         vs.push_back( word );
    33.     }
    34.  
    35.     e = str.find_last_of( " " ) + 1;
    36.     vs.push_back( str.substr( e ) );
    37. }
    38.  
    39.  
    40. int main()
    41. {
    42.     const string expr  = "Alpha = ( Beta & Xichma )";
    43.     const string delim = " ";
    44.     vecstr       my_data;
    45.  
    46.     cut_string( expr, my_data, delim );
    47.     copy( my_data.begin(), my_data.end(), ostream_iterator< string >( cout, "\n" ) );
    48.  
    49.     return 0;
    50. }

  5. #5
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    không nhớ nick này của ai nữa,hình như của CN2,cậu đang chứng minh lại WFF ah???
    bài của anh rook_rox làm trên codeblock nên nếu cậu không dùng các trình biên dịch chuẩn mới sẽ không dịch được đâu,bọn mình đang học Tubor C++ thì tớ khuyên cậu nên dùng theo cách này
    1. Vấn đề đầu tiên mình gặp phải là độ dài của chuỗi ký tự đó ko cố định, nó tùy thuộc vào người nhập vì thế minh định dùng mảng nhưng cũng ko được ổn lắm vì biết dùng mảng kích thước bao nhiêu cho đủ? Còn nếu dung con trỏ thì mình ko biết xin cấp phát thế nào (vì đâu có bít kích thước). Mong các bạn chỉ giúp.
    -> đầu tiên,nếu cậu không biết kích thước của mảng string bao nhiêu cậu có thể cấp phát động cho nó,không sao hết dùng new delete như thường

    2. Vấn đề thứ hai là việc tách lấy các chuỗi con của chuỗi ban đầu. Yêu cầu của thuật toán là phải tách lấy chuỗi con Beta cân bằng ngoặc.
    việc tách chuỗi cũng đơn giản thôi,cậu cho chạy từ đầu đến cuối nếu gặp dấu ( thì dừng lại tiếp tục xây thêm 1 vòng lặp nữa từ nơi i vừa dừng khi đến dấu ) thì dừng vòng lặp ( break nha )và tự xây 1 hàm copy xâu từ điểm i đến điểm j cậu vừa tìm được,cứ tiếp tục vòng lặp như vậy cậu sẽ có 1 mảng xâu nữa -> xâu đó chính là xâu đã tách ra

    nếu cậu vẫn không làm được mình sẽ post code

    Code:
    //ho va ten : Nguyen Huy Son
    //Lop D07CNTT3
    
    #include "iostream.h"
    #include "string.h"
    #include "conio.h"
    int kiemtra2ngoi(char menhde[1000],int n);
    int canbangngoac(char menhde[1000],int n);
    void kiemtramenhde(char menhde[1000]);
    int main()
    {
    	char menhde[1000];
    	
    	cout<<"\n                        Define in Computer \n\n"<<"\n v   define    or\n\n ^   define    and \n -   define    not\n i   define    if,then \n o   define    if and only if\n";
    	cout<<" 1 Menh De don la 1 Ky Hieu VD nhu A,B,C...\n ";
            cout<<"\n VD Menh De ((A^B)vC)i(Dv(-C))  tuong duong voi ((A^B)VC)->(Dv(-C))\n";
    	cout<<"\nImput WFF:";
    	cin.getline(menhde,1000);
            if((menhde[0]!='('&&strlen(menhde)!=1)||(menhde[0]=='('&&strlen(menhde)==1))
    	{
    	   cout<<"\n menh de phai chua trong dau ngoac\n";
    	   return 0;
            }
    	kiemtramenhde(menhde);
    	return 0;
    }
    int kiemtra2ngoi(char menhde[1000],int n)
    {
    	for (int i=0;i<n-2;i++)
    	{
    		if (menhde[i]=='^'||menhde[i]=='v'||menhde[i]=='o'||menhde[i]=='i')
    		{
    			if (menhde[i+1]=='(')
    			{
    				for(int j=i+1;j<n;j++)
    				{
    					if
    
    (menhde[j]==')'&&(menhde[j+1]=='^'||menhde[j+1]=='v'||menhde[j+1]=='o'||menhde[j+1]=='i')&&menhde[j-1]!=')')
    					{
    						return -1;
    					}
    				}
    			}
    			else
    			{
    				if
    
    (menhde[i+2]!=menhde[i]&&(menhde[i+2]=='^'||menhde[i+2]=='v'||menhde[i+2]=='o'||menhde[i+2]=='i'))
    				{
    					return -1;
    				}
    			}
    		}
    	}
    	return 0;
    }
    int canbangngoac(char menhde[1000],int n)
    {
    	int save =0,i,j,test =0;
    	for(i =0;i<n;i++)
    	{
    	    if(menhde[i] == '(')
    	    {
    	        test = save + 1;
    	        for(j = 1+ save;j<n;j++)
    	        {
    	            if(menhde[j]== ')')
    	            {
    	                save = j;     //luu lai vi tri tim ra can bang ngoac
    	                break;
                    }
                }
                if(save == test -1 )    // vi da dat  test = save + 1;
                {
                    return -1;  //vi thieu dau ngoac )
                }
            }
            else if(menhde[i] == ')')
            {
    	            test = save - 1;
    	            for(j = - 1 + save;j>=0;j--)
    	            {
    	                if(menhde[j]== '(')
    	                {
    	                    save = j;     //luu lai vi tri tim ra can bang ngoac
    	                    break;
                        }
                     }
                     if(save == test + 1 )    // vi da dat  test = save + 1;
                     {
                          return -1;  //vi thieu dau ngoac )
                     }
            }
        }
        return 0;
    }
    void kiemtramenhde(char menhde[1000])
    {
    	int n=strlen(menhde);
    	if (menhde[n-1]=='^'&&menhde[n-1]=='v'&&menhde[n-1]=='o'&&menhde[n-1]=='i')
    	{
    		cout<<"menh de sai do toan tu o vi tri cuoi cung\n";
    		getch();
    		return ;
    	}
    	if (menhde[0]=='^'||menhde[0]=='v'||menhde[0]=='o'||menhde[0]=='i')
    	{
    		cout<<"menh de bat dau bang toan tu\n";
    		getch();
    		return ;
    	}
    	for(int i=0;i<n;i++)
    	{
    		if(menhde[i]=='(')
    		{
    			if (menhde[i+1]=='^'||menhde[i+1]=='v'||menhde[i+1]=='o'||menhde[i+1]=='i')
    			{
    				cout<<"menh de sai do ( va toan tu phia sau gan nhau\n";
    		                getch();
    				return ;
    			}
    			else if(i>0&&menhde[i-1]!='^'&&menhde[i-1]!='v'&&menhde[i-1]!='o'&&menhde[i-1]!='i'&&menhde[i-1]!='-'&&menhde[i-1]!='(')
    			{
    				cout<<"menh de sai do khong co toan tu truoc dau (\n";
    				getch();
    				return ;
    			}
    		}
    		else if (menhde[i]==')')
    		{
    			if (menhde[i-1]=='^'||menhde[i-1]=='v'||menhde[i-1]=='o'||menhde[i-1]=='i')
    			{
    				cout<<"menh de sai do ) va toan tu phia truoc gan nhau\n";
    		                getch();
    				return ;
    			}
    			else if
    
    (i<n-1&&menhde[i+1]!='^'&&menhde[i+1]!='v'&&menhde[i+1]!='o'&&menhde[i+1]!='i'&&menhde[i+1]!=')')
    			{
    				cout<<"menh de sai do khong co toan tu sau dau )\n";
    				getch();
    				return ;
    			}
    		}
    		else if (menhde[i]=='^'||menhde[i]=='v'||menhde[i]=='o'||menhde[i]=='i')//neu toan tu
    		{
    			if (menhde[i-1]=='^'||menhde[i-1]=='v'||menhde[i-1]=='o'||menhde[i-1]=='i')
    			{
    				cout<<"menh de sai do 2 toan tu sat nhau \n";
    		                getch();
    				return ;
    			}
    		}
    		else if (menhde[i]!='^'&&menhde[i]!='v'&&menhde[i]!='o'&&menhde[i]!='i')
    		{
    			if(menhde[i-1]!='^'&&menhde[i-1]!='v'&&menhde[i-1]!='o'&&menhde[i-1]!='i'&&i>0&&menhde[i-2]!=')'&&menhde[i-1]!='('&&menhde[i-1]
    
    !='-')
    			{
    				cout<<"menh de sai,menh de thu "<<i <<" sat nhau voi menh de "<<i-1<<"\n";
    		                getch();
    				return ;
    			}
    		}
    	}
    	if (canbangngoac(menhde,n)==0&&kiemtra2ngoi(menhde,n)==0)
    	{
    		int dem =0,demtoantu=0;
    		for(i=0;i<n;i++)
    		{
    			if (menhde[i]=='(')
    			{
    				dem++;
    			}
    			else if (menhde[i]=='v'||menhde[i]=='^'||menhde[i]=='i'||menhde[i]=='o')
    			{
    				demtoantu++;
    			}
    		}
    		if (demtoantu>dem)
    		{
    			cout<<"menh de sai thieu dau ngoac ngoai cung";
    			getch();
    			return;
    		}
    		cout<<"menh de da dung\n";
    		getch();
    	    return ;
    	}
    	else if(canbangngoac(menhde,n)==-1)
    	{
    		cout<<"menh de sai do khong can bang ngoac\n";
    		getch();
    	    return ;
    	}
    	else
    	{
    		cout<<"menh de sai do logic chi co phep toan 2 ngoi \n";
    		getch();
    	    return ;
    	}
    	return ;
    }
    chạy trên TC nha,thầy bắt thế mà
    Đã được chỉnh sửa lần cuối bởi AlexF : 15-12-2008 lúc 03:39 PM.

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

  1. nghĩa của 3 từ "principals", "artifacts", "securables" là như thế nào?
    Gửi bởi ntbao trong diễn đàn English for IT | Tiếng anh cho dân CNTT
    Trả lời: 2
    Bài viết cuối: 02-09-2017, 06:36 PM
  2. Lỗi"error C2275: 'T' : illegal use of this type as an expression" khi dùng "list<T>::iterator it"
    Gửi bởi doicanhden trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 6
    Bài viết cuối: 19-01-2012, 01:59 AM
  3. Trả lời: 1
    Bài viết cuối: 01-12-2011, 07:32 PM
  4. Problems : " recover tree " with input as " preorder" and "inorder"
    Gửi bởi HoangManhHa1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 13-04-2011, 10:19 PM
  5. Logic "củ chuối"
    Gửi bởi hien_seominar1 trong diễn đàn Giải trí - Thư giãn
    Trả lời: 0
    Bài viết cuối: 08-04-2011, 11:05 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