Search…

Ứng Dụng Stack - Biểu Thức Tiền Tố (Prefix)

20/08/20203 min read
Trong toán học thì các biểu thức thường được biểu diễn dưới dạng trung tố (Infix) cho dễ hiểu. Đó là đối với con người còn đối với máy tính thì nó khó hiểu đối với chúng. Nhưng đối với máy tính thì chúng đưa biểu thức về dạng tiền tố (Prefix) rồi sau đó tính toán.

Trong toán học thì các biểu thức thường được biểu diễn dưới dạng trung tố (các toán tử nằm giữa các toán hạng). Đối với máy tính thì khó sử dụng để tính toán, phải đưa biểu thức dạng trung tố về dạng tiền tố hoặc hậu tố.

Khái niệm về biểu thức tiền tố?

Biểu thức tiền tố (Prefix) là thuật toán được biểu diễn bằng cách đặt các toán tử trước các toán hạng.

Ví dụ minh hoạ:

Infix Prefix
x * y + z +*xyz
x * (y - z) *-yzx

Thuật toán chuyển từ trung tố sang tiền tố

Ví dụ có biểu thức trung tố sau: (A + B) * D - E

  1. Đảo ngược biểu thức lại như sau:  E-D*)B+A(
  2. Đổi dấu ( thành )) thành (.
  3. Chuyển biểu thức sang hậu tố (Posfix) theo dạng.
Expression Stack Output
E-D*)B+A( Empty  
-D*)B+A( Empty E
D*)B+A( - E
*)B+A( -* ED
)B+A( -* ED
B+A( -*) ED
+A( -*) EDB
A( -*)+ EDB
( -*)+ EDBA
    EDBA+*-

Posfix: EDBA+*-

Đảo lại biểu thức hậu tố thì sẽ có được biểu thức tiền tố như sau.

Prefix: -*+EDBA

Tính giá trị biểu thức tiền tố

  1. Đảo biểu thức tiền tố.
  2. Duyệt từ trái sang phải và dùng hàm isdigit() kiểm tra nếu là toán hạng thì đưa vào trong chuỗi.
  3. Đổi chuỗi thành số và đưa vào trong Stack.
  4. Tiếp tục duyệt nếu là toán tử thì lấy lần lượt 2 phần tử trên nhất của Stack ra tính toán và đưa kết quả tính được vào lại Stack.
  5. Thực hiện cho đến khi gặp kí tự \0 kết thúc chuỗi.
  6. Kết quả của biểu thức chính là phần tử còn lại cuối cùng trong Stack.

Code demo

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

int precedence(char c)
{
	if (c == '*' || c == '/' || c == '%')
		return 2;
	else
	{
		if (c == '+' || c == '-')
			return 1;
		else
			return 0;
	}
}

Chuyển từ trung tố sang tiền tố

// Reverse expression
void setExpression(Stack* A, char* str)
{
	A->inf = str;
	strrev(A->inf);
	A->len = strlen(A->inf);
	*(A->Prefix + A->len) = '\0';
	A->pre = A->Prefix + (A->len - 1);
}

void convert(Stack* A)
{
	char oper;
	while(*(A->inf))
	{
		if(*(A->inf) == ' ')
		{
			A->inf++ ;
			continue;
		}
		else if(isdigit(*(A->inf)) || isalpha(*(A->inf)))
		{
			while(isdigit(*(A->inf)) || isalpha(*(A->inf)))
			{
				*(A->pre) = *(A->inf);
				A->inf++ ;
				A->pre-- ;
			}
			*(A->pre) = ' ';
			A->pre--;
		}
		else if(*(A->inf) ==')')
		{
			Push (A, *(A->inf));
			A->inf++;
		}
		else if(*(A->inf) == '*' || *(A->inf) == '+' || *(A->inf) == '/' || *(A->inf) == '%' || *(A->inf) =='-')
		{
			if(A->top != -1)
			{
				oper = Pop(A);
				while(precedence(oper) > precedence(*(A-> inf)))
				{
					*(A->pre) = oper;
					A->pre--;
					oper= Pop (A);
				}
				Push(A,oper);
				Push(A, *(A->inf));
			}
			else
				Push(A, *(A->inf));
			A->inf++;
  		}
		else if(*(A->inf) == '(')
		{
			oper = Pop(A);
			while(oper != ')')
			{
				*(A->inf) = oper;
				A->pre--;
				oper = Pop(A);
			}
			A->inf++ ;
		}
	}
	while(A->top != -1)
	{
		oper = Pop(A);
		*(A->pre) = oper;
		A-> pre--;
	}
	A->pre++;
}

Tính giá trị biểu thức tiền tố

int calculateValue(sta* B)
{
	int value, operand= 0;
	while(*(B->left_to_right))
	{
		if(isdigit(*(B->left_to_right)))
		{
			while(isdigit(*(B->left_to_right)))
			{
				*(B->right_to_left) = *(B->left_to_right);
				operand = operand * 10 + *(B->right_to_left) - '0';
				B->left_to_right++;
				B->right_to_left--;
			}
			push_sta(B, operand);
		}
		else
		{
			switch(*(B->left_to_right))
			{
			case '+':
				value = pop_sta(B) + pop_sta(B);
				break;
			case '-':
				value = pop_sta(B) - pop_sta(B);
				break;
			case '/':
				value = pop_sta(B) / pop_sta(B);
				break;
			case '*':
				value = pop_sta(B) + pop_sta(B);
				break;
			case '%':
				value = pop_sta(B) % pop_sta(B);
				break;
			}
			push_sta(B,value);
		}
		B->left_to_right++;
	}
	value = pop_sta(B);
	return value;
}

Bài chung series

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024