자료구조 <스택, 응용:괄호검사, 후위표기수식계산>

스택 기본구성

#include <iostream>
#include <string>

using namespace std;

template <class T>
class stack {
	int top;
	
	T* array;
public:
	stack() { top = -1;}
	~stack() { delete[]array; }
	void create(int size) {
		array = new T[size];
		

	}

	void push(T element) {
		array[++top]=element;

	}
	T pop() {
		T res;
		res = array[top];
		top--;
		return res;

	}
	T peak() {
		return array[top];
	}
	int _size() {
		return top + !;
	}
	bool is_empty() {
		if (top == -1)return true;
		else return false;
	}

};


int main() {
	stack<int> test;
	int size = 5;
	test.create(size);
	test.push(1);
	test.push(2);
	test.push(3);
	cout << test.pop() << endl;
	cout << test.peak() << endl;
	cout << test.pop() << endl;
}

c++로 구현한 템플릿 stack 클래스이며 동적 할당으로 스택의 전체 크기를 정한다. 잘못된 부분이 있으면 수정하도록 하자. 

---

스택의 응용 : 괄호 검사

 

#include <iostream>
#include <string>

using namespace std;
#define  MAX_POWER 10000

template <class T>
class Stack {
	T array[MAX_POWER];
	int top;
public:
	Stack() {
		top = -1;

	}
	void push(T element) {
		array[++top] = element;

	}
	T pop() {
		T arr = array[top];
		top--;
		return arr;
	}
	int size() {
		int _size = top + 1;
		return _size;

	}
	bool is_empty() {
		if (size() == 0)return true;
		return false;
	}
	T peak() {
		T arr = array[top];
		return arr;
	}
};
int test(const char *line) {
	int size = strlen(line);
	Stack<char> v;

	for (int i = 0; i < size; i++) {
		char ch = line[i];
		switch (ch)
		{
		case '(':case'[':case'{':
			v.push(ch); break;
		case ')':case']':case'}':
		{
			if (v.size() == 0)return 0;
			char rech = v.pop();
			if (
				(rech == '('&&ch != ')')
				|| (rech == '{'&&ch != '}')
				|| (rech == '['&&ch != ']')
				) return 0;
			else break;
		}
		}
	}
	if (v.is_empty())return 1;
	else return 0;
}


int main() {
	const char *line = "{A[(i+1)]=0;}";
	if (test(line) == 1)cout << "괄호검사 통과 ";
	else cout << "괄호검사 오류";
}

 

괄호검사 다이어그램

---

후위표기식 계산

#include <iostream>
#include <string>

using namespace std;
#define  MAX_POWER 10000

template <class T>
class Stack {
	T array[MAX_POWER];
	int top;
public:
	Stack() {
		top = -1;

	}
	void push(T element) {
		array[++top] = element;

	}
	T pop() {
		T arr = array[top];
		top--;
		return arr;
	}
	int size() {
		int _size = top + 1;
		return _size;

	}
	bool is_empty() {
		if (size() == 0)return true;
		return false;
	}
	T peak() {
		T arr = array[top];
		return arr;
	}
};

int test(const char *exp)
{
	int size = strlen(exp);
	Stack<char> v;
	int op1, op2;
	int result;
	for (int i = 0; i < size; i++) {
		char ch = exp[i];
		switch (ch)
		{
		case '/': 
			op2 = v.pop();
			op1 = v.pop();
			result = (int)op1 / op2;
			v.push(result);
			break;
		case '*':
			op2 = v.pop();
			op1 = v.pop();
			result = (int)op1 * op2;
			v.push(result);
			break;
		case '-':
			op2 = v.pop();
			op1 = v.pop();
			result = (int)op1 - op2;
			v.push(result);
			break;
		case '+':
			op2 = v.pop();
			op1 = v.pop();
			result = (int)op1 + op2;
			v.push(result);
			break;
		default:
			int m = ch - '0';
			v.push(m);
			break;
		}
	}
	result = v.pop();
	return result;
}
int main() {
	const char *exp = "82/3-32*+";
	cout << test(exp) << endl;
}

후위표기계산 다이어그램

후위표기계산의 시간복잡도는 O(n)

---

중위 표기식을 후위표기 수식으로 바꾸는 프로그램

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define  MAX_POWER 10000

template <class T>
class Stack {
	T array[MAX_POWER];
	int top;
public:
	Stack() {
		top = -1;

	}
	void push(T element) {
		array[++top] = element;

	}
	T pop() {
		T arr = array[top];
		top--;
		return arr;
	}
	int size() {
		int _size = top + 1;
		return _size;

	}
	bool is_empty() {
		if (size() == 0)return true;
		return false;
	}
	T peak() {
		if (top == -1)return NULL;
		T arr = array[top];
		return arr;
	}
};
int prio(char x)
{
	if (x == '(')return 0;
	else if (x == '+' || x == '-')return 1;
	else if (x == '*' || x == '/')return 2;

	return 0;
}
vector<char> test(const char exp[])
{
	vector<char> cexp;
	int size = strlen(exp);
	Stack<char> v;
	char _ch;
	for (int i = 0; i < size; i++)
	{
		char ch = exp[i];
		switch (ch) {
		case '+':case'-':
			if (prio(ch) <= prio(v.peak())) {
				_ch = v.pop();
				cexp.push_back(_ch);
				v.push(ch);

			}
			else v.push(ch);
			break;
		case '*':case'/':
			v.push(ch);
			break;
		case '(':
			v.push(ch);
			break;
		case ')':
			_ch = v.pop();
			cexp.push_back(_ch);
			while (_ch != '(') {
				_ch = v.pop();
				if (_ch != '(')cexp.push_back(_ch);
			}
			break;
		default:
			cexp.push_back(ch);


		}

	}
	
		if (!(v.is_empty())) {
			_ch = v.pop();
			cexp.push_back(_ch);
		}
		
		
		return cexp;

	

}

int main() {
	const char *exp = "(2+3)*4+9";
	vector<char> arr = test(exp);
	int size = arr.size();
	for (int i = 0; i < size; i++)
	{
		cout << arr[i];
	}
}

다양한 구현을 위해 단순 print출력이 아닌 vector STL을 이용하여 구현한 코드이다.

중위표기->후위표기식 전환 다이어그램