STDIO
Tìm kiếm gần đây

    Nội dung

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

    18/01/2017
    25/07/2020
    Ứ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++.

    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 *

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

    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

    Thảo luận

    Đăng nhập

    Bài viết liên quan

    Ứng Dụng Stack - Biểu Thức Trung Tố (Infix)

    Ứng Dụng Stack - Biểu Thức Trung Tố (Infix)

    Ứng dụng Stack trong bài toán trung tố, hậu tố và tiền tố là một trong những ứng dụng quan trọng của Stack và là một vấn đề hay đối với bạn đọc. Trong đó bài toán về ...

    Tran Khanh Nguyen

    02/04/2017

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

    Ứ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ố ( Infix ) cho dễ hiểu. Đó là đối với con người còn đối với máy tính thì nó khó hiểu đối với ...

    Phạm Hoài Nguyên

    19/08/2016

    Ứng Dụng Nhận Diện Biển Số Xe: Xây Dựng Giao Diện - Phần 2

    Ứng Dụng Nhận Diện Biển Số Xe: Xây Dựng Giao Diện - Phần 2

    Bài viết nằm trong loạt bài viết tự học OpenCV qua ví dụ thực tế. Ứng dụng nhận diện biển số xe là một ứng dụng rất có ý nghĩa trong thực tế, nó giúp cho việc quản lý, ...

    Trương Xuân Đạt

    23/01/2015

    Ngôn Ngữ C++ - Lịch Sử Hình Thành Và Phát Triển

    Ngôn Ngữ C++ - Lịch Sử Hình Thành Và Phát Triển

    C++ là một ngôn ngữ lập trình đa dụng – ta có thể dùng C++ để lập trình cho các hệ thống lớn, lập trình hệ điều hành cho đến các ứng dụng, game hay thậm chí ta có thể ...

    Vũ Quang Huy

    27/09/2014

    Ứng Dụng Nhận Diện Biển Số Xe: Xây Dựng Giao Diện - Phần 1

    Ứng Dụng Nhận Diện Biển Số Xe: Xây Dựng Giao Diện - Phần 1

    Bài viết nằm trong loạt bài viết tự học OpenCV qua ví dụ thực tế. Ứng dụng nhận diện biển số xe là một ứng dụng rất có ý nghĩa trong thực tế, nó giúp cho việc quản lý, ...

    Trương Xuân Đạt

    23/01/2015

    Firefox OS - Phát Triển Ứng Dụng - Và Thế Giới Của Mozilla

    Firefox OS - Phát Triển Ứng Dụng - Và Thế Giới Của Mozilla

    Firefox OS đã ngừng phân phối vào 8/2015. Bên cạnh đó, bài viết này giới thiệu về cách thức triển khai 1 project HTML5 lên thiết bị chạy Firefox OS xem như tài liệu tham ...

    La Kiến Vinh

    18/09/2014

    Linked List - Stack - Queue

    Linked List - Stack - Queue

    Giới thiệu về các cấu trúc dữ liệu và ứng dụng của Linked list - Stack - Queue.

    Hiếu Nguyễn

    18/11/2014

    Hiệu Ứng Camera Shake Trong Unity

    Hiệu Ứng Camera Shake Trong Unity

    Đối với các game hành động nhập vai, các hiệu ứng âm thanh hấp dẫn, hiệu ứng về ánh sáng, sự kịch tính, yếu tố bất ngờ, ... đóng vai trò không nhỏ trong sự thành công của ...

    Rye Nguyen

    06/08/2015

    Vector Và Ứng Dụng Của Chúng

    Vector Và Ứng Dụng Của Chúng

    Vector là một khái niệm rất quen trong toán học; và chúng được ứng dụng trong rất nhiều lĩnh vực khác nhau: đồ họa máy tính, mô phỏng vật lý … Bài viết này muốn giới ...

    Vũ Quang Huy

    26/09/2014

    C# Script - Lớp Random

    C# Script - Lớp Random

    Các yếu tố ngẫu nhiên là điều cơ bản và là nền tảng để xây dựng nên trí thông minh nhân tạo (AI) trong game, ngoài ra còn được sử dụng để tạo nên điều bất ngờ trong một ...

    Rye Nguyen

    07/08/2015

    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
    [email protected]

    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 - 2020