STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    Ứng Dụng Stack - Biểu Thức Trung Tố (Infix)

    Ứng dụng ngăn xếp stack để xử lý các biểu thức trung tố (Infix).
    02/04/2017 20/08/2020 5 phút đọc
    Ứng Dụng Stack - Biểu Thức Trung Tố (Infix)

    Về cơ bản, biểu thức trung tố là 1 phương pháp biểu diễn toán học thường gặp. Ví dụ:

    • 1 + 2 * (3 - 4)
    • a * 7 + 8 * (8 - b)

    Khái niệm bài toán trung tố

    Ký pháp trung tố là:

    • Phương pháp biểu diễn phép toán 2 ngôi.
    • Một phép toán 2 ngôi trên tập X là một ánh xạ f: X x X → X cho (a, b)f(a, b) thuộc A.
      • Ánh xạ f khi đó thường được kí hiệu bởi *, được gọi là toán tử, các phần tử a, b được gọi là các hạng tử (hay toán hạng).
    • Khi viết biểu thức biểu diễn phép toán đó, đặt ký hiệu toán tử ở giữa các toán hạng. Ví dụ: a + b, a – b, a * b, ... khi biểu thức có nhiều phép toán, dùng các cặp dấu ngoặc ( ) và thứ tự ưu tiên các phép toán để chỉ rõ thứ tự thực hiện các phép toán.
      • Nguyên tắc ưu tiên là *, /, %, ^ có độ ưu tiên cao hơn +, -.

    Thuật toán

    Giả sử M là một biểu thức được cho ở dạng trung tố. Khởi tạo 2 Stack: ShSt.

    Stack Sh dùng để lưu trữ toán hạng, stack St dùng để lưu trữ toán tử.

    Duyệt M từ trái qua phải:

    • Nếu M[i] là toán hạng thì đưa vô Sh.
    • Nếu M[i]( thì đưa vô St.
    • Nếu M[i] là toán tử có độ ưu tiên cao hơn toán tử hiện có trên đỉnh St thì đưa nó vào St.
    • Nếu M[i] là toán tử có độ ưu tiên thấp hơn hoặc bằng toán tử hiện có trên đỉnh St thì lấy 2 toán tử trên đỉnh Sh thực hiện phép tính với toán tử là phần tử trên đỉnh của St, kết quả cất vào Sh. Sau đó cất M[i] vào St.
    • Nếu M[i] là dấu ) , nếu phần tử trên đỉnh St khác ( thì thực hiện phép tính với toán tử là phần tử trên đỉnh của St, kết quả cất vào Sh. Loại dấu ngoặc ( gặp phải đầu tiên ra khỏi St.
    • Thực hiện đến khi nào St rỗng và Sh còn 1 phần tử duy nhất đó là kết quả.

    Chạy thử thuật toán

    Cho M = 5 * 3 – (3 + 5)

    1.  Khởi tạo Sh = {} và St = {}
    2. M1 = "5" -> Đưa vào Sh. Sh={ 5 } St={} 3. M2 = "*" -> Đưa vào St. Sh={ 5 } St={ * } 4. M3 = "3" -> Đưa vào Sh. Sh={ 5 3 } St={ * } 5. M4 = "-" -> Tính 5 * 3 = 15 Sh={ 15 } St={ - } 6. -> Đưa vào Sh. 7. M5 = "(" -> Đưa vào St. Sh={ 15 } St={ - ( } 8. M6 = "3" -> Đưa vào Sh. Sh={ 15 3 } St={ - ( } 9. M7 = "+" -> Đưa vào St. Sh={ 15 3 } St={ - ( + } 10. M8 = "5" -> Đưa vào Sh. Sh={ 15 3 5 } St={ - ( + } 11. M9 = "(" -> Tính 3 + 5 = 8 Sh={ 15 8 } St={ - } 12. -> Đưa vào Sh. 13. Top(St) = "-" -> Tính 15-8=7 Sh={ 7 } St={} 14. -> Đưa vào Sh. 15. Dừng.

    Một số hàm quan trọng

    Xét độ ưu tiên toán tử

    int UT(string x)
    {
    	if(x == "sqrt" || x == "^")
    	    return 3;  
    
    	if (x == "*" || x == "/" || x == "%" || x == "^" || x == "sqrt")
    		return 2;
    	else if (x == "+" || x == "-")
    		return 1;
    	else if (x == "(")
    		return 0;
    
    	return -1;
    }

    Kiểm tra là toán hạng hay toán tử

    int HT(string x)
    {
    	if (x == "*" || x == "/" || x == "%" || x == "+" || x == "-" || x == "^" || x == "sqrt")
    		return 2;
    	else
    		return 1;
    }

    Hàm tính giá trị của phép toán

    string calculateValue(string b, string x, string a)
    {	
    	float fResult = 0;
    
    	if(x=="sqrt")
    	{
    		 fResult = int(sqrt(atof(a.c_str())));
    	}
    	if(x=="^")
    	{
    		fResult=1;
    		for(int i =1 ;i<=int(atof(a.c_str()));i++)
    			fResult = fResult*atof(b.c_str());
    	}
    	if(x=="%")
    	{
    		 fResult = int(atof(b.c_str())) % int(atof(a.c_str()));
    	}
    	if (x == "*")
    	{
    		fResult = atof(b.c_str()) * atof(a.c_str());
    	}
    	else if (x == "/")
    	{
    		fResult = atof(b.c_str()) / atof(a.c_str());
    	}
    	else if (x == "+")
    	{
    		fResult = atof(b.c_str()) + atof(a.c_str());
    		
    	}
    	else if (x == "-")
    	{
    		fResult = atof(b.c_str()) - atof(a.c_str());
    	}
    
    	string strResult=to_string (fResult);
    	return strResult;
    }

    Hàm thực hiện thuật toán

    float calculateValue(vector<string> M)
    {
    	float fResult = 0;
    
    	Stack* Sh = new Stack(); 
    	Stack* St = new Stack(); 
    
    	int iLength=M.size(); 
    
    	for (int i = 0; i < iLength; i++)
    	{
    		if (HT(M[i]) == 1 && M[i] != "(" && M[i] != ")")
    			Sh->Push(M[i]);
    
    		if (M[i] == "(")
    			St->Push(M[i]);
    
    		if (HT(M[i]) == 2) 
    		{
    			while (!St->IsEmpty() && (UT(M[i]) <= UT(St->GetHead()->Info))) 
    			{
    				string a = "";
    				Sh->Pop(a);       
    				string x = "";
    				St->Pop(x);       
    				string b = "";
    				Sh->Pop(b);      
    				Sh->Push(this->calculateValue(b, x, a));   
    			}
    			St->Push(M[i]); 
    		}
    
    		if (M[i] == ")") 
    		{
    			while (St->GetHead()->Info != "(") 
    			{
    				string a = "";
    				Sh->Pop(a);       
    				string x = "";
    				St->Pop(x);       
    				string b = "";
    				Sh->Pop(b);      
    				Sh->Push(this->calculateValue(b, x, a));   
    			}
    			string c = "";
    			St->Pop(c);   
    		}
    	}
    
    	while (!St->IsEmpty())
    	{	
    		string a = "";
    		Sh->Pop(a);      
    		string x = "";
    		St->Pop(x);      
    		string b = "";
    		Sh->Pop(b);      
    		Sh->Push(this->calculateValue(b, x, a));   
    	}
    
    	string strResult = "";
    	Sh->Pop(strResult); 
    	fResult = atof(strResult.c_str());
    	return fResult;
    }

    Download demo

    Infix.zip

    Bài chung series

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021