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

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ạ:

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 ) và ) thành (.
3. Chuyển biểu thức sang hậu tố (Posfix) theo dạng.

Đả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

• Ứ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)