Ứng dụng ngăn xếp stack để chuyển từ biểu thức trung tố (infix) sang hậu tố (postfix) và tính giá trị biểu thức là một ứng dụng rất quan trọng và cần thiết đối với bạn đọc.
Data Structure & Algorithm Nguyễn Thị Trúc Linh 2015-12-05 05:20:52

Giới thiệu

Các biểu thức đại số sử dụng hằng ngày đượ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 phải 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ố. Trong bài viết này, tôi sẽ 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ạ:

Infix

Postfix

A / B – C * D

A B / C D * +

A / ( B – C * D)

A B C D * - /

A / (B – C) * D

A B C - / D *

Các phương thức trên Stack

Ở bài viết này, tôi trình bày cách tính toán biểu thức hậu tố dùng kĩ thuật Stack. Việc xây dựng cấu trúc Stack, các hàm cơ bản của Stack các bạn có thể tham khảo thêm bài viết Stack - Ngăn Xếp của tác giả Jason Bùi.

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

STDIO_Postfix