Biểu Thức Hậu Tố 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 Biểu Thức 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 Biểu Thức Hậu Tố

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;
}

Tham khảo thêm

• • • LQDOJ
    • Stack và ứng dụng