SPOJ.COM - Thuật toán bài ONP - Transform the Expression

Đề bài:

Biến đổi biểu thức đại số sau thành dạng "kí pháp nghịch đảo Ba Lan" (RPN : Reverse Polish Notation). Hay nói cách khác là biến đổi biểu thức từ dạng trung tố thành dạng hậu tố. Trong đó, các toán tử hai ngôi: +, -, , /, ^ (có độ ưu tiên từ thấp nhất lên cao nhất), dấu ngoặc (), toán hạng chỉ bao gồm chữ cái a, b, c,...z. Giả sử rằng chỉ có một dạng RPN, không có trường hợp kiểu như ab*c.

Đầu vào

T [số lượng biểu thức <= 100]

Biểu thức [độ dài <= 400]

[Những biểu thức khác] Thành phần ở trong dấu [] không xuất hiện ở đầu vào.

Đầu ra

Các biểu thức dạng RPN, mỗi cái trên một dòng.

Ví dụ

Đầu vào:

3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Đầu ra:

abc*+
ab+zx+*
at+bac++cd+^*

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/ONP/

Phân tích

• Đây là bài toán cơ bản, có thể xếp vào bài toán sử dụng thuật toán tham lam Greedy.

• Thuật toán biến đổi biểu thức trung tố thành dạng hậu tố sử dụng Stack là:

  • Nếu là toán hạng: cho ra output.
  • Nếu là dấu mở ngoặc "(": cho vào stack
  • Nếu là dấu đóng ngoặc ")": lấy các toán tử trong stack ra và cho vào output cho đến khi gặp dấu mở ngoặc "(". (Dấu mở ngoặc cũng phải được đưa ra khỏi stack)
  • Nếu là toán tử:
    • Chừng nào ở đỉnh stack là toán tử và toán tử đó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì lấy toán tử đó ra khỏi stack và cho ra output.
    • Đưa toán tử hiện tại vào stack Sau khi duyệt hết biểu thức trung tố, nếu trong stack còn phần tử thì lấy các thành phần trong đó ra và cho lần lượt vào output. (Tham khảo tại: YinYang's Programming Blog)

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

const int MAX = 405;

// Trả về true nếu kí tự ch là toán hạng
bool IsOperand(char ch)
{
	return (ch >= 'a' && ch <= 'z');
}

// Trả về true nếu kí tự ch là toán tử
bool IsOperator(char ch)
{
	if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^') return true;
	return false;
}

// Trả về độ ưu tiên cho các toán tử
int GetPriority(char ch)
{
	if(ch == '+') return 1;
	if(ch == '-') return 2;
	if(ch == '*') return 3;
	if(ch == '/') return 4;
	if(ch == '^') return 5;
	return -1;
}

// Trả về độ dài xâu str
int GetLength(char *str)
{
	int length = 0;
	while(str[length] != '\0') length++;
	return length;
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("input.txt","r",stdin);

	int T = 0;
	char str[MAX];

	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		cin >> str;
		int length = GetLength(str);

		char *stack = new char[length + 1];
		int st_size = 0;

		// Thực hiện theo thuật toán
		for(int i = 0; i < length; i++)
		{
			if(IsOperand(str[i]))
			{
				cout << str[i];
			}
			else if(str[i] == '(')
			{
				stack[st_size++] = str[i];
			}
			else if(str[i] == ')')
			{
				while (stack[st_size-1] != '(')
				{
					cout << stack[st_size-1];
					st_size--;
				}
				st_size--;
			}
			else if(IsOperator(str[i]))
			{
				while(IsOperator(stack[st_size-1]) &&
				        (GetPriority(stack[st_size-1]) >= GetPriority(str[i])))
				{
					cout << stack[st_size-1];
					st_size--;
				}

				stack[st_size] = str[i];
				st_size++;
			}
		}
		cout << endl;
		delete[] stack;
	}
	return 0;
}