Ứ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: Sh và St.

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] là ( 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

• Ứng Dụng Stack - Biểu Thức Trung Tố (Infix)
• Ứng Dụng Stack - Biểu Thức Hậu Tố (Postfix)
• Ứng Dụng Stack - Biểu Thức Tiền Tố (Prefix)