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 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 chúng. Nhưng đối với máy tính thì chúng đưa biểu thức về dạng tiền tố (Prefix) rồi sau đó tính toán.
    19/08/2016 20/08/2020 3 phút đọc
    Ứ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ố (các toán tử nằm giữa các toán hạng). Đối với máy tính thì khó sử dụng để tính toán, phải đưa biểu thức dạng trung tố về dạng tiền tố hoặc hậu tố.

    Khái niệm về biểu thức tiền tố?

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

    Ví dụ minh hoạ:

    Infix Prefix
    x * y + z +*xyz
    x * (y - z) *-yzx

    Thuật toán chuyển từ trung tố sang tiền tố

    Ví dụ có biểu thức trung tố sau: (A + B) * D - E

    1. Đảo ngược biểu thức lại như sau:  E-D*)B+A(
    2. Đổi dấu ( thành )) thành (.
    3. Chuyển biểu thức sang hậu tố (Posfix) theo dạng.
    Expression Stack Output
    E-D*)B+A( Empty  
    -D*)B+A( Empty E
    D*)B+A( - E
    *)B+A( -* ED
    )B+A( -* ED
    B+A( -*) ED
    +A( -*) EDB
    A( -*)+ EDB
    ( -*)+ EDBA
        EDBA+*-

    Posfix: EDBA+*-

    Đảo lại biểu thức hậu tố thì sẽ có được biểu thức tiền tố như sau.

    Prefix: -*+EDBA

    Tính giá trị biểu thức tiền tố

    1. Đảo biểu thức tiền tố.
    2. Duyệt từ trái sang phải và dùng hàm isdigit() kiểm tra nếu là toán hạng thì đưa vào trong chuỗi.
    3. Đổi chuỗi thành số và đưa vào trong Stack.
    4. Tiếp tục duyệt nếu là toán tử thì lấy lần lượt 2 phần tử trên nhất của Stack ra tính toán và đưa kết quả tính được vào lại Stack.
    5. Thực hiện cho đến khi gặp kí tự \0 kết thúc chuỗi.
    6. Kết quả của biểu thức chính là phần tử còn lại cuối cùng trong Stack.

    Code demo

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

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

    Chuyển từ trung tố sang tiền tố

    // Reverse expression
    void setExpression(Stack* A, char* str)
    {
    	A->inf = str;
    	strrev(A->inf);
    	A->len = strlen(A->inf);
    	*(A->Prefix + A->len) = '\0';
    	A->pre = A->Prefix + (A->len - 1);
    }
    
    void convert(Stack* A)
    {
    	char oper;
    	while(*(A->inf))
    	{
    		if(*(A->inf) == ' ')
    		{
    			A->inf++ ;
    			continue;
    		}
    		else if(isdigit(*(A->inf)) || isalpha(*(A->inf)))
    		{
    			while(isdigit(*(A->inf)) || isalpha(*(A->inf)))
    			{
    				*(A->pre) = *(A->inf);
    				A->inf++ ;
    				A->pre-- ;
    			}
    			*(A->pre) = ' ';
    			A->pre--;
    		}
    		else if(*(A->inf) ==')')
    		{
    			Push (A, *(A->inf));
    			A->inf++;
    		}
    		else if(*(A->inf) == '*' || *(A->inf) == '+' || *(A->inf) == '/' || *(A->inf) == '%' || *(A->inf) =='-')
    		{
    			if(A->top != -1)
    			{
    				oper = Pop(A);
    				while(precedence(oper) > precedence(*(A-> inf)))
    				{
    					*(A->pre) = oper;
    					A->pre--;
    					oper= Pop (A);
    				}
    				Push(A,oper);
    				Push(A, *(A->inf));
    			}
    			else
    				Push(A, *(A->inf));
    			A->inf++;
      		}
    		else if(*(A->inf) == '(')
    		{
    			oper = Pop(A);
    			while(oper != ')')
    			{
    				*(A->inf) = oper;
    				A->pre--;
    				oper = Pop(A);
    			}
    			A->inf++ ;
    		}
    	}
    	while(A->top != -1)
    	{
    		oper = Pop(A);
    		*(A->pre) = oper;
    		A-> pre--;
    	}
    	A->pre++;
    }
    

    Tính giá trị biểu thức tiền tố

    int calculateValue(sta* B)
    {
    	int value, operand= 0;
    	while(*(B->left_to_right))
    	{
    		if(isdigit(*(B->left_to_right)))
    		{
    			while(isdigit(*(B->left_to_right)))
    			{
    				*(B->right_to_left) = *(B->left_to_right);
    				operand = operand * 10 + *(B->right_to_left) - '0';
    				B->left_to_right++;
    				B->right_to_left--;
    			}
    			push_sta(B, operand);
    		}
    		else
    		{
    			switch(*(B->left_to_right))
    			{
    			case '+':
    				value = pop_sta(B) + pop_sta(B);
    				break;
    			case '-':
    				value = pop_sta(B) - pop_sta(B);
    				break;
    			case '/':
    				value = pop_sta(B) / pop_sta(B);
    				break;
    			case '*':
    				value = pop_sta(B) + pop_sta(B);
    				break;
    			case '%':
    				value = pop_sta(B) % pop_sta(B);
    				break;
    			}
    			push_sta(B,value);
    		}
    		B->left_to_right++;
    	}
    	value = pop_sta(B);
    	return value;
    }

    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