Viết thuật toán chuyển biểu thức từ trung tố sang hậu tố

c++

(aduka) #1

Đề bài: Chuyển biểu thức từ trung tố sang hậu tố.

Mô tả:
Đọc biểu thức từ trái qua phải 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), 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.

Sau khi duyệt hết biểu thức infix, nếu trong stack còn phần tử thì lấy các token trong đó ra và cho lần lượt vào output

Yêu cầu dùng ngôn ngữ c++ để giải bài toán trên. anh chị giúp em với ạ


(Ngô Anh Đức) #2

stack chỉ dùng để mô phỏng bài này cho dễ hiểu thôi chứ thực ra dùng 1 cái biến đếm + if-else là xong.

Bài này trước đây mình làm đây.

//File stack.h
#ifndef stackm_h
#define stackm_h
const int MAX_STACK = 100;
typedef char stackItemType;
class stack
{
public:
	stack();
	stack(const stack & astack);
	~stack();
	bool isEmpty()const;
	void push(stackItemType stacktop);
	void pop();
	void pop(stackItemType &astack);
	void getStackTop(stackItemType &stacktop)const;
	//void display();
	int UuTien(char c);
	void HauTo();
private:
	struct stackNode{
		stackItemType item;
		stackNode *next;
	};
	stackNode *topPtr;
};
#endif


//File stack.cpp
#include "stack.h"
#include <assert.h>
#include <iostream>
#include <string>
using namespace std;
stack::stack()
{
}
stack::stack(const stack & astack)
{
	if (astack.topPtr == NULL)
	{
		topPtr = NULL;
	}
	else
	{
		topPtr = new stackNode;
		assert(topPtr != NULL);
		topPtr->item = astack.topPtr->item;
		stackNode *newPtr = topPtr;
		for (stackNode *orgPtr = astack.topPtr->next; orgPtr != NULL; orgPtr = orgPtr->next)
		{
			newPtr->next = new stackNode;
			assert(newPtr->next != NULL);
			newPtr = newPtr->next;
			newPtr->item = orgPtr->item;

		}
		newPtr->next = NULL;
	}
}

stack::~stack()
{
	while (!isEmpty())
		pop();
}

bool stack::isEmpty() const
{
	return topPtr == NULL;
}
void stack::push(stackItemType newItem)
{
	stackNode *newPtr = new stackNode;
	if (newPtr == NULL)
		cout << "Khong thue duoc vung nho";
	else
	{
		newPtr->item = newItem;
		newPtr->next = topPtr;
		topPtr = newPtr;
	}
}
void stack::pop()
{
	if (isEmpty())
		cout << "stack rong" << endl;
	else
	{
		stackNode *temp = topPtr;
		topPtr = topPtr->next;
		temp->next = NULL;
		delete temp;
	}
}
void stack::pop(stackItemType &stackTop)
{
	if (isEmpty())
		cout << "stack rong" << endl;
	else
	{
		stackTop = topPtr->item;
		stackNode *temp = topPtr;
		topPtr = topPtr->next;
		temp->next = NULL;
		delete temp;
	}
}
void stack::getStackTop(stackItemType &stackTop)const
{
	if (isEmpty())
		cout << "stack rong" << endl;
	else
		stackTop = topPtr->item;
}
/*void stack::display()
{
cout << "Phan tu trong stack la:" << endl;
while (!isEmpty())
{
cout << topPtr->item << "\n";
topPtr = topPtr->next;
}
}*/

int stack::UuTien(char c)
{
	if (c == '^')
		return 3;
	if (c == '*' || c == '/' || c == '%')
		return 2;
	if (c == '+' || c == '-')
		return 1;
	else return 0;
}
void stack::HauTo()
{
	stack s;
	int i = 0;
	char c;
	string str, str1 = "";
	cout << "Nhap bieu thuc trung to:";
	getline(cin, str);
	while (i < str.length())
	{
		c = str.at(i);
		if (c - '0' >= 0 && c - '0' <= 9 || isalpha(c))
			str1 += c;
		else
		{
			cout << str1 << " ";
			str1 = "";
			if (c == '(')
				s.push(c);
			else
			{
				if (c == ')')
				{
					while (s.getStackTop(c) != '(')
					{
						cout << s.getStackTop(c);
						s.pop();
					}
					s.pop();
				}
				else
				{
					while (!s.isEmpty() && UuTien(c) <= UuTien(s.getStackTop(c)))
					{
						cout << s.getStackTop(c);
						s.pop();
					}
					s.push(c);
				}
			}
		}
	}
	if (str1 != "")
		cout << str << " ";
	while (!s.isEmpty())
	{
		cout << s.getStackTop(c);
		s.pop();
	}
}

89% Thành viên có cách giải cho một câu hỏi. Bạn thì sao?