Ứng Dụng Stack - Biểu Thức Hậu Tố (Postfix)

Các biểu thức đại số được biểu diễn dưới dạng trung tố (Infix). Tuy nhiên, để máy tính tính được giá trị của một biểu thức thì cần biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố. Bài viết trình bày về cách chuyển từ biểu thức trung tố (Infix) sang hậu tố (Postfix) và tính toán biểu thức hậu tố bằng kỹ thuật Stack.

Postfix là gì?

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

Một vài ví dụ minh hoạ:

Thuật toán chuyển từ trung tố sang hậu tố

1. Khởi tạo Stack rỗng.
2. Khởi tạo 2 chuỗi x và token; i, j lần lượt là index của Infix và Postfix.
3. Duyệt vòng lặp for từ i = 1 cho đến cuối chuỗi Infix:
   • Nếu Infix[i] là toán hạng thì đưa vào Postfix.
   • Nếu Infix[i] là toán tử thì Push vào ngăn xếp S.
   • Nếu Infix[i] là “)” thì Pop vào ngăn xếp S (lấy giá trị trên đỉnh của S) sau đó đưa vào Postfix.

Output: Postfix là biểu thức hậu tố.

Tính giá trị biểu thức hậu tố

Duyệt biểu thức dạng chuỗi từ trái sang phải:

Dùng hàm isdigit để kiểm tra:

• Nếu là toán hạng thì dùng Push() đưa vào ngăn xếp S.
• Nếu là toán tử thì Pop() 2 toán hạng trong ngăn xếp S ra, sau đó tính toán giá trị của chúng dựa vào toán tử này, sau đó Push() lại vào S.
• Thực hiện cho đến khi gặp kí tự \0 kết thúc chuỗi.
• Kết quả của biểu thức chính là phần tử còn lại cuối cùng trong ngăn xếp S.

Code demo

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

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

	return 3;
}

Chuyển từ trung tố sang hậu tố

void infixtoPostfix(char infix[], char postfix[])
{
	Stack S;
	char x, token;
	int i = 0, j = 0;    // i-index of infix,j-index of postfix
	init(&S);
	for (i = 0; infix[i] != '\0'; i++)
	{
		token = infix[i];
		if (isalnum(token))
			postfix[j++] = token;
		else
			if (token == '(')
				Push(&S, '(');
			else
				if (token == ')')
					while ((x = Pop(&S)) != '(')
						postfix[j++] = x;
				else
				{
					while (precedence(token) <= precedence(top(&S)) && !isEmpty(&S))
					{
						x = Pop(&S);
						postfix[j++] = x;
					}
					Push(&S, token);
				}
	}

	while (!isEmpty(&S))
	{
		x = Pop(&S);
		postfix[j++] = x;
	}

	postfix[j] = '\0';
}

Tính giá trị biểu thức hậu tố

float Evaluate(char *Postfix)
{
	struct Stack S;
	char *p;
	float op1, op2, result;
	S.TOP = -1; 
	p = &Postfix[0];
	while (*p != '\0')
	{
		while (*p == ' ' || *p == '\t')
		{
			p++;
		}
		if (isdigit(*p))
		{
			int num = 0;
			while (isdigit(*p))
			{
				num = num * 10 + *p - 48;
				*p++;
			}
			Push(&S, num);
		}
		else
		{
			op1 = Pop(&S);
			op2 = Pop(&S);
			switch (*p)
			{
			case '+':
				result = op2 + op1;
				break;
			case '-':
				result = op2 - op1;
				break;
			case '/':
				result = op2 / op1;
				break;
			case '*':
				result = op2 * op1;
				break;
			default:
				printf("\nInvalid Operator");
				return 0;
			}
			Push(&S, result);
		}
		p++;
	}
	result = Pop(&S);
	return result;
}

Download demo

Postfix.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)