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.
Data Structure & Algorithm Phạm Hoài Nguyên 2015-12-05 16:40:23

Giới thiệu

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) 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. Vì vậy, để hiểu được máy tính phải đưa biểu thức dạng trung tố về dạng tiền tố hoặc hậu tố. Trong bài viết này tôi trình bày cách đưa biểu thức dạng trung tố về dạng tiền tố và tính toán biểu thức tiền 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.

Các 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ố

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

1. Ta đảo ngược biểu thức lại như sau:       E-D*)B+A(

2. Đổi dấu ‘(‘ thành ‘)’ và ’)’ 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+*-

4. Đảo lại biểu thức hậu tố thì ta 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 Priority(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 Set_Expr(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(Priority(oper) > Priority(*(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 Calculate_Value(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;
}