STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

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

    Ứng dụng ngăn xếp stack để chuyển từ biểu thức trung tố (Infix) sang hậu tố (Postfix) và code mẫu tính giá trị biểu thức với C++.
    18/01/2017 19/08/2020 3 phút đọc
    Ứ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ạ:

    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 *

    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

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021