[전공]/[자료구조]

[C++ 자료구조론] 3장 스택과 큐

danhan 2022. 10. 30. 01:41

템플릿 template

  • 클래스와 함수의 재사용에 기여
  • 템플릿/ 인수화 타입을 이용해 소프트웨어 개발 시간과 비용 절약

SelectionSort

  • 선택 정렬 기법을 이용해 n ≥1 개의 서로 다른 T의 집합을 정렬
  • 사용 시 주의사항
    • 사용자 정의 데이타 타입에 대해서는 별도로 정의해야 한다.
template <class T> // 이 부분을 반드시 넣어야 한다.
void SelectionSort(T *a, const int n) {
	// n개의 T a[0]부터 a[n-1]까지 비감소 순으로 정렬한다.
	for ( int i = 0; i < n; i++) {
		int j = i;
		// a[i]와 a[n-1] 사이에 가장 작은 T를 찾는다
		for (int k = i + 1; k < n; k++)
			if (a[k] < a[j]) j = k;
		swap(a[i], a[j]);
	}
}

ChangeSize1D

  • 1-dim array의 크기 변경하는 템플릿 함수
ㅠtemplate <class T>
void ChangeSize1D(T *& a, const int oldSize, const int newSize) {
	if (newSize < 0) throw “New length must be >= 0”;
	T* temp = new T[newSize]; // 새로운 배열 
	int number = min(oldSize, newSize);  // 복사할 원소 수 
	copy(a, a + number, temp);
	delete [] a;  // 이전 메모리를 제거
	a = temp;
}

 

컨테이너 클래스

  • 다수의 데이타 객체들을 수용 또는 저장하는 자료 구조를표현하는 클래스

백 Bag

  • 동일한 원소가 여러 번 나타남
  • 원소 위치, 삭제 연산 시 어떤 원소가 제거되는지는 문제 안됨
  • 삽입(Push): 해당 원소를 배열의 첫번째 가용 위치에 저장. 배열이만원인 경우 그 크기를 두 배 확장.
  • 삭제(Pop): 배열 중앙 위치 원소 삭제. 그 오른쪽 모든 원소는 한자리씩 왼쪽으로 이동.
  • Element: 삭제될 원소를 반환
  • 구현
  • template <class T> class Bag { public: Bag (int bagCapacity = 10); ~Bag(); int Size() const; bool IsEmpty() const; T& Element() const; // element한개 반환 void Push(const T&); void Pop(); private: T *array; int capacity; int top; }

스택 Stack

💡 top에서 모든 삽입과 삭제가 일어나는 순서 리스트

  • 후입 선출 LIFO 리스트
  • 구현
Template <class T>
Class Stack { //0개 이상의 원소를 가진 유한 순서 리스트.
Public:
	Stack(int stackCapacity = 10); // 처음크기 stackCapacity 공백 스택 생성
	bool IsEmpty() const; // 스택 원소 수가 0이면 true, 아니면 false를 반환
	T& Top() const; //스택의 톱 원소를 반환
	void Push(const T& item) ; // 스택의 톱에 item을 삽입
	void Pop(); // 스택의 톱 원소를 삭제
private:
	T *stack; // 스택 원소를 위한 배열
	int top; // 톱 원소의 위치
	int capacity; // 스택 배열의 크기
};
 
template <class T>
Stack<T>::Stack (int stackCapacity): capacity (stackCapacity) {
	if(capacity < 1) throw “Stack capacity must be > 0”;
	stack = new T[capacity];
	top = -1;
}
 
template <class T>
inline bool Stack<T>::IsEmpty() const { return top == -1; }
 
template <class T>
inline T& Stack<T>::Top() const {
	if (IsEmpty()) throw “Stack is empty”;
	return stack[top];
}
 
template <class T>
void Stack<T>::Push(const T& x) { // Add x to the stack
	if (top == capacity – 1) {
		ChangeSize1D(stack, capacity, 2*capacity);
		capacity *= 2;
	}
	stack[++top] = x;
}
 
template <class T>
void Stack<T>::Pop() { // Delete top element from the stack.
	if (IsEmpty()) throw “Stack is empty. Cannot delete.”;
	stack[top--].~T(); // destructor for T
}

시스템 스택

  • 프로그램 실행 시 함수 호출을 처리
  • 함수 호출 시 스택 프레임 구조 또는 활성 레코드를 생성해 시스탬 스택의 top에 둔다.
    • 이전의 스택 프레임에 대한 포인터
    • 복귀 주소
    • 지역 변수
    • 매개 변수


서브 타입

  • 상속 inheritance : 추상 데이타 타입간의 서브타입(subtype)관계를 표현
  • IS-A(~의 하나이다) 관계
  • Stack은 Bag의 서브타입
    • 백(bag): 단순히 원소들이 삽입과 삭제가 될 수 있는 자료구조 -기본 클래스
    • 스택: 원소들이 후입선출 순서에 따라 삭제되는 자료 구조(제한적) - 파생 클래스
  • 상속의 의미
    • 파생 클래스(Stack)가 기본 클래스(Bag)의 모든 멤버(데이타와 함수)들을 상속받음
      • 단, 기본 클래스의 private 멤버는 접근 불가능
    • 상속된 멤버들은 기본 클래스에서 가졌던 것과 똑같은접근 레벨을 파생클래스에서도 가짐
    • 상속 받은 멤버함수는 똑같은 프로토 타입(prototype)을 유지함

실습 코드

bagstack.h

using namespace std;
 
class Bag {
public:
	Bag(int bagCapacity = 10); // 생성자
	virtual ~Bag();            // 파괴자
 
	virtual int Size() const;  // 백에 있는 원소 수를 반환
	virtual bool IsEmpty() const; // 백이 공백이면 true, 아니면 false를 반환
	virtual int Element() const;  // 백에 있는 원소를 반환
 
	virtual void Push(const int);
	virtual void Pop();
 
	friend ostream& operator<<(ostream&, Bag&);
protected:
	int* array;
	int capacity;  // 배열의 크기
	int top;       // 톱 원소의 배열 위치
};
 
class Stack : public Bag {
public:
	Stack(int stackCapacity = 10);
	~Stack();
	int Top() const;
	void Pop();
};
 
void ChangeSize1D(int*& a, const int oldsize, const int newSize);

bagstack.cpp

#include <algorithm>
#include <iostream>
using namespace std;
#include "bagstack.h"
 
Bag::Bag(int bagCapacity) : capacity(bagCapacity) {
	if (capacity < 1) throw "Capacity must be > 0";
	array = new int[capacity];
	top = -1;
}
 
Bag::~Bag() { delete [] array; }
 
// 함수 호출의 오버헤드를 제거하기 위해 짧은 길이 코드는 inline으로 선언
// 백에 있는 원소 수를 반환
inline int Bag::Size() const { return top + 1; }
// 백이 공백이면 true, 아니면 false를 반환
inline bool Bag::IsEmpty() const { return Size() == 0; }
// 백에 있는 첫 번째 원소를 반환
inline int Bag::Element() const {
	if (IsEmpty()) throw "Bag is empty";
	return array[0];
}
 
// 백에 정수를 삽입
// T가 대형 객체일 때 생기는 부하를 막기위해 매개변수를 상수 참조함
// void Bag::Push(const T & x)
void Bag::Push(const int x) {
	// 할당된 메모리가 꽉 찼으면 용량을 2배로 늘림
	if (capacity == top + 1) {
		ChangeSize1D(array, capacity, 2 * capacity);
		capacity *= 2;
	}
	// 전위 연산 주의!
	array[++top] = x;
}
 
void ChangeSize1D(int*& a, const int oldsize, const int newSize) {
	if (newSize < 0) throw "New length must be >= 0";
	// 새로운 배열
	int* temp = new int[newSize]; 
	// 복사할 원소 수
	int number = std::min(oldsize, newSize); 
	copy(a, a + number, temp);
	// 이전 메모리를 제거
	delete[] a; 
	a = temp;
}
 
void Bag::Pop() {
	if (IsEmpty()) throw "Bag is empty, cannot delete";
	int deletePos = top / 2;
	// 배열 정리 - 가운데 원소를 삭제한다.
	copy(array + deletePos + 1, array + top + 1, array + deletePos); 
	top--;
	// array[top--].~T();
}
 
Stack::Stack(int stackCapacity) :Bag(stackCapacity) {}
Stack::~Stack() { }
 
int Stack::Top() const {
	if (IsEmpty()) throw "Stack is empty";
	return array[top];
}
 
void Stack::Pop() {
	if (IsEmpty()) throw "Stack is empty. Cannot delete";
	top--;
}
 
ostream& operator<<(ostream& os, Bag& b) {
	for (int i = 0; i <= b.top; i++)
		os << b.array[i] << " ";
	os << endl;
	return os;
}
#include <iostream>
using namespace std;
#include "bagstack.h"
 
int main() {
	Bag b(3);
	Stack s(3);
 
	b.Push(1); b.Push(2); b.Push(3); b.Push(4); b.Push(5);
	cout << "Bag: " << b ;
	// Bag: 1 2 3 4 5
 
	s.Push(1); s.Push(2); s.Push(3); s.Push(4); s.Push(5);
	cout << "Stack: " << s <<endl ;
	// Stack: 1 2 3 4 5
 
	b.Pop(); s.Pop();
	cout << "Bag: "<< b ;
	cout << "Stack: " << s << endl<<endl;
	// Bag: 1 2 4 5
	// Stack: 1 2 3 4
 
	int j = s.Size(); //Stack의 부모클래스 Bag의 Size()가 불려진다
	cout << "Stack 크기: " << j << endl;
	j = s.Top(); //Stack의 Top()가 불려진다
	cout << "Stack Top() 결과: " << j << endl;
	j = s.Element(); //Stack의 부모클래스 Bag의 Element()가 불려진다
	cout << "Stack Element() 결과: " << j << endl<< endl;
	// Stack 크기: 4
	// Stack Top() 결과: 4
	// Stack Element() 결과: 1
}

 

큐 queue

 💡 rear에서 삽입이 일어나고 front에서 삭제가 일어나는 순서 리스트

  • 새로운 원소가 삽입되는 끝 - rear
  • 원소가 삭제되는 끝 - front
  • 선업선출 FIFO 리스트
  • 구현
    • 첫 번째 원소가 queue[0]일 때
      • 삭제(pop) : queue[0]에 있는 앞 원소를 제거
        • 삭제할 때마다 나머지 원소들을 왼쪽으로 이동해야 함
        • 큐가 n개의 원소를 가질 때, 삭제 시 Θ(n) 시간이 걸림
      • 삽입(push) : 배열 크기 조절 시간을 제외하면 Θ(1) 시간이 걸림
    • 첫 번째 원소가 queue[front]일 때
      • 변수 front를 사용하여 큐의 첫번째 위치를 항상 유지
      • 원소를 삭제해도 다른 원소들을 이동할 필요가 없음
      • 삭제를 Θ(1) 시간에 수행 가능

원형 큐 Circular queue

  • queue[front]로 표현한 큐에서 rear가 capacity-1과 같고, front > 0 일 때 배열의 크기를 확장해야한다.
  • 이때 큐가 배열의 끝에서 되돌아오게 하면 큐에 저장되는 원소들은 모두 시계 방향으로 저장된다.
    • capacity-1의 다음 위치 = 0
    • 0의 직전 위치 = capacity-1
  • 변수 front는 큐에서 첫 원소의 위치보다 반시계방향으로 하나 앞위치를 가리킴
  • 변수 rear는 큐에서 마지막 원소의 위치를 가리킴
  • 구현
private:
	T* queue; // 큐 원소를 위한 배열 (heap영역에 위치)
	int front, // 첫번째 원소로부터 반시계 방향으로 한 위치 뒤
	rear, // 마지막 원소의 위치
	capacity; // 현재 확보된 큐 배열의 크기
 
template <class T>
Queue<T>::Queue (int queueCapacity): capacity (queueCapacity) {
	if(capacity < 1) throw “Queue capacity must be > 0”;
	// front == rear가 공백인지 포화인지 구분하기 위해
	// 최대 원소 수를capacity가 아니라 capacity-1로 한다
	queue = new T[capacity];
	front = rear = 0;
}
 
// 큐의 공백 조건 : front == rear
template <class T>
inline bool Queue<T>::IsEmpty() { return front == rear; }
 
Template <class T>
Inline T& Queue<T>::Front() {
	if(IsEmpty()) throw “Queue is empty. No front element”;
	return queue[(front+1)%capacity];
}
 
Template <class T>
Inline T& Queue<T>::Rear() {
	if(IsEmpty()) throw “Queue is empty. No rear element”;
	return queue[rear];
}
  • push 구현
    1. 크기가 두배 되는 새로운 배열 newQueue를 생성한다.
    2. 두번째 부분(즉, queue[front+1]과 queue[capacity-1] 사이에 있는 원소들)을 newQueue의 0에서부터 복사해 넣는다.
    3. 첫번째 부분(즉 queue[0]와 queue[rear]사이에 있는 원소들)을 newQueue의 capacity-front-1에서부터 복사해 넣는다
    		template <class T>
    		void Queue<T>::Push(const& x) {// add x at rear of queue.
    			if ((rear + 1) % capacity == front)	{
    				// queue capacity 2배 확장 코드
    				T* newQueue = new T[2*capacity];
    				// copy from queue to new Queue
    				int start = (front+1) % capacity;
    		 
    				if (start < 2) // no wrap around
    					copy(queue+start, queue+start+capacity-1, newQueue);
    				else {
    					copy(queue+start, queue+capacity, newQueue);
    					copy(queue, queue+rear+1, newQueue+capacity-start);
    				}
    				// switch to newQueue
    				front = 2*capacity – 1; rear = capacity-2; capacity *= 2;
    				delete [] queue;
    				queue = newQueue;
    			}
    			rear = (rear+1)%capacity;
    			queue[rear] =x; 
    		}
  • pop 구현
template <class T>
void Queue<T>::Pop() {// 큐로부터 원소를 삭제한다. 
	if(isEmpty()) throw “Queue is empty. Cannot delete.”;
	front = (front+1)%capacity;
	queue[front].~T(); // T를 위한 파괴자
}

 

 

미로 maze

  • 1≤i≤m이고 1≤j≤p인 이차원 배열 maze[m][p]로 표현
  • 1 : 통로가 막혀 있음, 0 : 통과할 수 있음
  • 경계선에 있는 경우 : i ==1, i == m , j==1, j == p 인 경우
    • 경계 조건을 매번 검사하지 않기 위해 미로의 주위를 1로 둘러쌈
    • 배열은 maze[m+2][p+2]로 선언
  • 이동 방향 미리 정의하는 방법

  • 구현

maze.cpp

#include <iostream>
#include <stack>
using namespace std;
 
const int MAXSIZE = 100;
bool maze[MAXSIZE + 2][MAXSIZE + 2];
bool mark[MAXSIZE + 1][MAXSIZE + 1] = { 0 };
enum directions { N, NE, E, SE, S, SW, W, NW };
 
struct offsets {
	int a, b;
}
movea[8] = { -1,0, -1,1, 0,1, 1,1, 1,0, 1,-1, 0,-1, -1,-1 };
 
struct Items {
	Items(int xx = 0, int yy = 0, int dd = 0) : x(xx), y(yy), dir(dd) {}
	int x, y, dir; // dir은 다음에 방문 예정인 방향
};
 
template <class T>
ostream& operator<< (ostream& os, stack<T>& s) {
	// 스택의 내용을 역순으로 출력
	stack<T> s2;
 
  // 내용을 하나씩 꺼내 다른 임시 스택에 넣어 저장한 후,
	while (!s.empty()) { s2.push(s.top()); s.pop(); }
 
	// 그 임시 스택에서 하나씩 꺼내 출력
	while (!s2.empty()) {
		os << " -> " << s2.top();
		s.push(s2.top()); s2.pop();
	}
	return os;
}
 
ostream& operator<<(ostream& os, Items& item) {
	// 5개의 Items가 출력될 때마다 줄 바꾸기 위한 변수
	static int count = 0;
 
	os << "(" << item.x << "," << item.y << ")";
	count++;
 
	if ((count % 5) == 0) cout << endl;
	return os;
}
 
void Path(const int m, const int p) {
	mark[1][1] = 1;
	// C++ STD stack을 이용하기
	stack<Items> stack;
	// (1,1)에서 E방향부터(시계방향) 순차적으로 시도함
	Items temp(1, 1, E);
	stack.push(temp);
 
	while (!stack.empty()) {
		temp = stack.top(); stack.pop();
		// (i,j)부터 (g,h)로 이동한다
		int i = temp.x; int j = temp.y; int d = temp.dir;
		while (d < 8) {
			int g = i + movea[d].a; int h = j + movea[d].b;
 
			if ((g == m) && (h == p)) { // 출구에 도착하면
				// 경로를 출력한다.
				cout << stack;
				// 경로 상의 마지막 두 위치
				temp.x = i; temp.y = j; cout << "->" << temp;
				temp.x = m; temp.y = p; cout << "->" << temp << endl;
				return;
			}
 
			// 방문하지 않은 새로운 위치라면
			if ((!maze[g][h]) && (!mark[g][h])) {
				// 방문했다고 표시한다.
				mark[g][h] = 1;
				// 현 위치와 실패 시 다음에 시도할 방향을 저장한다.
				temp.x = i; temp.y = j; temp.dir = d + 1;
				stack.push(temp);
				// (g, h)로 이동한다. N방향부터 시계방향으로 시도하자.
				i = g; j = h; d = N;
			}
			else d++;
		}
	}
	cout << "No path in maze." << endl;
}
 
void getdata(istream& is, int& m, int& p) {
	// 자료화일을 읽어들여 maze에 저장한다
	is >> m >> p;
	for (int i = 0; i < m + 2; i++) { maze[i][0] = 1; maze[i][p + 1] = 1; }
	for (int j = 1; j <= p; j++) { maze[0][j] = 1; maze[m + 1][j] = 1; }
 
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= p; j++)
			is >> maze[i][j];
}
#include <iostream>
#include <fstream>
using namespace std;
 
void getdata(istream&, int&, int&);
void Path(int, int);
 
int main(int argc, char* argv[]) {
	int m, p; // m by p maze
 
	if (argc == 1)
		cerr << "Usage: " << argv[0] << " maze_data_file" << endl;
	else {
		ifstream is(argv[1]);
		if (!is) { cerr << argv[1] << " does not exist\\n"; exit(1); }
		cout << "For maze datafile (" << argv[1] << ")\\n";
		getdata(is, m, p); is.close();
		Path(m, p);
	}
}
 
12 15
0 1 0 0 0 1 1 0 0 0 1 1 1 1 1
1 0 0 0 1 1 0 1 1 1 0 0 1 1 1
0 1 1 0 0 0 0 1 1 1 1 0 0 1 1
1 1 0 1 1 1 1 0 1 1 0 1 1 0 0
1 1 0 1 0 0 1 0 1 1 1 1 1 1 1
0 0 1 1 0 1 1 1 0 1 0 0 1 0 1
0 0 1 1 0 1 1 1 0 1 0 0 1 0 1
0 1 1 1 1 0 0 1 1 1 1 1 1 1 1
0 0 1 1 0 1 1 0 1 1 1 1 1 0 1
1 1 0 0 0 1 1 0 1 1 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 1 1 1 1 0
0 1 0 0 1 1 1 1 1 0 1 1 1 1 0
 
For maze datafile (mazein.txt)
 -> (1,1) -> (2,2) -> (1,3) -> (1,4) -> (1,5)
 -> (2,4) -> (3,5) -> (3,4) -> (4,3) -> (5,3)
 -> (6,2) -> (7,2) -> (8,1) -> (9,2) -> (10,3)
 -> (10,4) -> (9,5) -> (8,6) -> (8,7) -> (9,8)
 -> (10,8) -> (11,9) -> (11,10) -> (10,11) -> (10,12)
 -> (10,13) -> (9,14) -> (10,15)->(11,15)->(12,15)

 

후위 표기식

  • 장점
    • 괄호가 불필요
    • 연산자의 우선 순위가 무의미
    • 계산 과정이 간단 (왼편에서 오른편으로 스캔)
  • 중위 표기식 → 후위 표기식 변환 알고리즘
    1. 식을 전부 괄호로 묶는다
    2. 이항 연산자들을 모두 자기 오른쪽 괄호로 이동시킨다.
    3. 괄호를 전부 삭제한다.
  • 연산자 우선 순위
    • 우선순위를 기반으로 스택에 push와 pop을 수행
    • ‘(‘ 의 우선순위가 문제임
    • 스택에 들어가기 전에는 가장 높은 우선순위의 연산자
    • 스택 속에 있을 때는 ‘)’가 나타날 때까지 낮은 우선순위의 연산자
    • so, 스택 top의 연산자의 isp가 새로운 연산자의 icp보다 산술적으로 작거나같을 때 스택에서 pop되어 출력
    • for (; isp(stack.Top()) <= icp(x); stack.Pop())
     

  • 예시

  • 구현
    • Expression e에 대한 NextToken(e)에서 unary – 와 binary –를 어떻게 구별하는가?
      • Infix Notation으로 된 Expression인 경우 Operand(피연산자) 후에 나온 –는 binary –이고, Operator(연산자) 후에 나온 –는 unary –이다. 단 맨 처음에 만난 –는 unary-로 간주한다.
      • Postfix Notation으로 된 Expression인 경우 입력자체가 binary –(-)와 unary –(-u)로 구별해야 함.

post.cpp

#include <iostream>
#include <stack>
#include "post.h"
using namespace std;
 
bool Token::operator==(char b) { return len == 1 && str[0] == b; }
bool Token::operator!=(char b) { return len != 1 || str[0] != b; }
 
Token::Token() {}
 
// 1-char token: type equals the token itself
Token::Token(char c) : len(1), type(c) {
	str = new char[1]; str[0] = c;
} // default type = c itself
 
// 2-char token(e.g. <=) & its type(e.g. LE)
Token::Token(char c, char c2, int ty) : len(2), type(ty) {
	str = new char[2]; str[0] = c; str[1] = c2;
}
 
//operand with its length & type(defaulted to ID)
Token::Token(char* arr, int l, int ty = ID) : len(l), type(ty) {
	str = new char[len + 1];
	for (int i = 0; i < len; i++) str[i] = arr[i];
	str[len] = '\\0';
 
	if (type == NUM) {
		ival = arr[0] - '0';
		for (int i = 1; i < len; i++) ival = ival * 10 + arr[i] - '0';
	}
	else if (type == ID) ival = 0;
	else throw "must be ID or NUM";
}
 
// 피연산자(ID 또는 NUM)인지 확인
bool Token::IsOperand() {
	return type == ID || type == NUM;
}
 
ostream& operator<<(ostream& os, Token t) {
	if (t.type == UMINUS) os << "-u";
	else if (t.type == NUM) os << t.ival;
	else for (int i = 0; i < t.len; i++) os << t.str[i];
	os << " ";
	return os;
}
 
bool GetID(Expression& e, Token& tok) {
	char arr[MAXLEN];  // ID 저장할 배열
	int idlen = 0;
	char c = e.str[e.pos];
 
	if (!(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')) return false;
 
	arr[idlen++] = c;
	e.pos++;
 
	while ((c = e.str[e.pos]) >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9') { 
		arr[idlen++] = c; e.pos++;
	}
	arr[idlen] = '\\0';
 
	tok = Token(arr, idlen, ID);
	return true;
}
 
bool GetInt(Expression& e, Token& tok) {
	char arr[MAXLEN];
	int idlen = 0;
	char c = e.str[e.pos];
 
	if (!(c >= '0' && c <= '9')) return false;
	arr[idlen++] = c;
	e.pos++;
 
	while ((c = e.str[e.pos]) >= '0' && c <= '9') { 
		arr[idlen++] = c; e.pos++;
	}
	arr[idlen] = '\\0';
 
	tok = Token(arr, idlen, NUM);
	return true;
}
 
void SkipBlanks(Expression& e) {
	char c;
	while (e.pos < e.len && ((c = e.str[e.pos]) == ' ' || c == '\\t'))
		e.pos++; 
}
 
// 두 글자 토큰들 처리: <= >= == != && || -u
bool TwoCharOp(Expression& e, Token& tok) {
	char c = e.str[e.pos]; char c2 = e.str[e.pos + 1];
	int op; // LE GE EQ NE AND OR UMINUS
	if (c == '<' && c2 == '=') op = LE;
	else if (c == '>' && c2 == '=') op = GE;
	else if (c == '=' && c2 == '=') op = EQ;
	else if (c == '!' && c2 == '=') op = NE;
	else if (c == '&' && c2 == '&') op = AND;
	else if (c == '|' && c2 == '|') op = OR;
	else if (c == '-' && c2 == 'u') op = UMINUS;
	else
		return false;
	tok = Token(c, c2, op); e.pos += 2;
	return true;
}
 
// 한 글자 토큰들 처리
bool OneCharOp(Expression& e, Token& tok) {
	char c = e.str[e.pos];
	if (c == '-' || c == '!' || c == '*' || c == '/' || c == '%' ||
		c == '+' || c == '<' || c == '>' || c == '(' || c == ')' || c == '=') {
		tok = Token(c); e.pos++;
		return true;
	}
	return false;
}
 
// 2nd arg=true for infix expression
Token NextToken(Expression& e, bool INFIX = true) {
	// 종전에 연산자 발견되었다고 가정
	static bool oprrFound = true; 
	Token tok;
 
	// 빈칸이 있다면 무시
	SkipBlanks(e);
 
	// 더 이상 남은 토큰이 없는 경우
	if (e.pos == e.len)
		{ if (INFIX) oprrFound = true; return Token('#'); }
 
	if (GetID(e, tok) || GetInt(e, tok)) 
		{ if (INFIX) oprrFound = false; return tok; }
 
	if (TwoCharOp(e, tok) || OneCharOp(e, tok)) {
		// 연산자 다음에 -가 나온 경우 -u로 바꿔라
		if (tok.type == '-' && INFIX && oprrFound)
			tok = Token('-', 'u', UMINUS);
 
		if (INFIX) oprrFound = true; return tok;
	}
	throw "Illegal Character Found";
}
 
// in-coming priority
int icp(Token& t) {
	int ty = t.type;
	int ty_num = -1;
 
	// ty가 '('면, 0, UMiNUS나 '!'면 1,'*'나 '/'나 '%'aus 2, '+'나 '-'면 3, '<'나 '>'나 LE나 GE면 4,
	//	EQ나 NE면 5, AND면 6, OR이면 7, '='이면 8,'#'면 9를 return 한다.
	if (ty == '(') ty_num = 0;
	else if (ty == UMINUS || ty == '!') ty_num = 1;
	else if (ty == '*' || ty == '/' || ty == '%') ty_num = 2;
	else if (ty == '+' || ty == '-') ty_num = 3;
	else if (ty == '<' || ty == '>' || ty == LE || ty == GE) ty_num = 4;
	else if (ty == EQ || ty == NE) ty_num = 5;
	else if (ty == AND) ty_num = 6;
	else if (ty == OR) ty_num = 7;
	else if (ty == '=') ty_num = 8;
	else if (ty == '#') ty_num = 9;
	else ty_num = -1;
 
	return ty_num;
}
 
//in-stack priority
int isp(Token& t) { 
	int ty = t.type;
	int ty_num = -1;
 
	// icp에서 (랑 #만 바뀜
	if (ty == '(') ty_num = 9;
	else if (ty == UMINUS || ty == '!') ty_num = 1;
	else if (ty == '*' || ty == '/' || ty == '%') ty_num = 2;
	else if (ty == '+' || ty == '-') ty_num = 3;
	else if (ty == '<' || ty == '>' || ty == LE || ty == GE) ty_num = 4;
	else if (ty == EQ || ty == NE) ty_num = 5;
	else if (ty == AND) ty_num = 6;
	else if (ty == OR) ty_num = 7;
	else if (ty == '=') ty_num = 8;
	else if (ty == '#') ty_num = 10;
	else ty_num = -1;
 
	return ty_num;
}
 
// 중위 표기식 e의 후위 표기식을 출력한다.
void Postfix(Expression e) {
	// 스택 초기화
	stack<Token> stack;
	// End Of String 표시
	stack.push('#');
 
	for (Token x = NextToken(e); x != '#'; x = NextToken(e))
		if (x.IsOperand()) cout << x;
		else if (x == ')') {
			// '('까지 스택에서 꺼낸다.
			for (; stack.top() != '('; stack.pop())
				cout << stack.top();
			// 'C'를 제거한다.
			stack.pop();
		} else { // x가 연산자일 떄
			for (; isp(stack.top()) <= icp(x); stack.pop()) {
				// 예외처리: a = b = 0 같은 우결합 연산자에선
				// 나중에 나온 = 이 우선순위가 높음.
				if (x == '=' && stack.top() == '=') break;
				cout << stack.top();
			}
			stack.push(x);
		}
 
	// 마지막 '#'의 출력은 생략한다.
	while (stack.top() != '#') { cout << stack.top(); stack.pop(); }
	stack.pop();
 
	cout << endl;
 
}

post.h

#ifndef POST_H
#define POST_H
// token types for non one-char tokens
#define ID 257
#define NUM 258
 
#define EQ 259
#define NE 260
#define GE 261
#define LE 262
#define AND 263
#define OR 264
#define UMINUS 265
#define MAXLEN 80
 
struct Expression {
	Expression(char* s) : str(s), pos(0) { for (len = 0; str[len] != '\\0'; len++); }
	char* str;
	int pos;
	int len;
};
struct Token {
	bool operator==(char);
	bool operator!=(char);
	Token();
	Token(char); // 1-char token: type equals the token itself
	Token(char, char, int); // 2-char token(e.g. <=) & its type(e.g. LE)
	Token(char*, int, int); //operand with its length & type(defaulted to ID)
	bool IsOperand(); // true if the token type is ID or NUM
 
	int type; // ascii code for 1-char op; predefined for other tokens
	char* str; // token value
	int len; // length of str
	int ival; // used to store an integer for type NUM; init to 0 for ID
};
 
using namespace std;
ostream& operator<<(ostream& os, Token t);
Token NextToken(Expression&, bool); // 2nd arg=true for infix expression
#endif
A * B * C
-A + B - C + D
A * -B + C
(A + B) * D + E / (F + A * D) + C
 
A B * C * 
A -u B + C - D + 
A B -u * C + 
A B + D * E F A D * + / + C +
A * B * C
-A + B - C + D
A * -B + C
(A + B) * D + E / (F + A * D) + C
 
A B * C * 
A -u B + C - D + 
A B -u * C + 
A B + D * E F A D * + / + C +
A && B||C||!(E>F)
!(A&&!((B<C)||(C>D)))||(C<E)
 
A B && C || E F > ! || 
A B C < C D > || ! && ! C E < ||
34 * 56 + 11 / 2
1 + 2 * 3 + - 4 * 2s
 
34 56 * 11 2 / + 
1 2 3 * + 4 -u 2 s * +
33 + 55 * 2
an77 = 2 + 7 * 5
b = 2
an77 + b * 2
a + 5
 
33 55 2 * + 
an77 2 7 5 * + = 
b 2 = 
an77 b 2 * + 
a 5 +

eval.cpp

#include <iostream>
#include <stack>
#include "post.h"
using namespace std;
 
int GetVal(Token& opnd) {
	if (opnd.type == NUM) return opnd.ival;
	return 0; // ID인 경우는 0을 return
}
 
// UMINUS와 ‘!’의 두가지 경우만 처리함
Token UnaryOp(int op, Token& x) {
	if (!x.IsOperand()) throw "Operand Only for Unary Operator";
	Token tmp; tmp.type = NUM;
 
	if (op == UMINUS) tmp.ival = -GetVal(x);
	else if (op == '!') tmp.ival = !GetVal(x);
	else throw "Invalid unary operator";
 
	return tmp;
}
 
Token BinaryOp(int op, Token& left, Token& right) {
	if (!left.IsOperand() || !right.IsOperand())
		throw "Two Operands required for Binary Operation";
 
	Token tmp; tmp.type = NUM;
	int val1 = GetVal(left), val2 = GetVal(right);
 
	if (op == '+') tmp.ival = val1 + val2;
	else if (op == '-') tmp.ival = val1 - val2;
	else if (op == '*') tmp.ival = val1 * val2;
	else if (op == '/') tmp.ival = val1 / val2;
	else if (op == '%') tmp.ival = val1 % val2;
	else if (op == '<') tmp.ival = val1 < val2;
	else if (op == '>') tmp.ival = val1 > val2;
	else if (op == GE) tmp.ival = val1 >= val2;
	else if (op == LE) tmp.ival = val1 <= val2;
	else if (op == EQ) tmp.ival = val1 == val2;
	else if (op == NE) tmp.ival = val1 != val2;
	else if (op == NE) tmp.ival = val1 && val2;
	else if (op == NE) tmp.ival = val1 || val2;
	else if (op == '=') throw "Assignment Not Yet Implemented";
	else throw "No such binary operator";
	return tmp;
}
 
// 스택의 top에 있는 것을 꺼내어 return한다.
Token DeleteFromStack(stack<Token>& stack) {
	if (stack.empty()) throw "Trying to pop from an empty stack";
 
	Token tmp = stack.top();
	stack.pop();
	return tmp;
}
 
// postfix 표현식을 입력으로 받아 그 값을 계산한다.
void Eval(Expression e) {
	stack<Token> stack;
	Token opnd1, opnd2;
	for (Token x = NextToken(e, false); x != '#'; x = NextToken(e, false))
		if (x.IsOperand()) stack.push(x);
		else { // x is an operator
			// unary operator
			if (x.type == UMINUS || x.type == '!') {
				opnd1 = DeleteFromStack(stack);
				stack.push(UnaryOp(x.type, opnd1));
			}
			else { // binary operator
				opnd1 = DeleteFromStack(stack);
				opnd2 = DeleteFromStack(stack);
				stack.push(BinaryOp(x.type, opnd2, opnd1));
			}
		}
 
	// 최종 계산 결과 출력
	cout << DeleteFromStack(stack) << endl;
}

posteval.cpp

#include <iostream>
#include "post.h"
using namespace std;
void Eval(Expression);
int main(void)
{
	char line[MAXLEN];
	while (cin.getline(line, MAXLEN)) {
		Expression e(line); // Assume postfix notation
 
		try {
			Eval(e);
		} catch (char const* msg) {
			cerr << "Exception: " << msg << endl;
		}
	}
}
 
34 56 * 11 2 / + 
1 2 3 * + 4 -u 2 * + 
33 55 2 * +
 
1909 
-1 
143
    1. )을 newQueue의 capacity-front-1에서부터 복사해 넣는다
    		template <class T>
    		void Queue<T>::Push(const& x) {// add x at rear of queue.
    			if ((rear + 1) % capacity == front)	{
    				// queue capacity 2배 확장 코드
    				T* newQueue = new T[2*capacity];
    				// copy from queue to new Queue
    				int start = (front+1) % capacity;
    		 
    				if (start < 2) // no wrap around
    					copy(queue+start, queue+start+capacity-1, newQueue);
    				else {
    					copy(queue+start, queue+capacity, newQueue);
    					copy(queue, queue+rear+1, newQueue+capacity-start);
    				}
    				// switch to newQueue
    				front = 2*capacity – 1; rear = capacity-2; capacity *= 2;
    				delete [] queue;
    				queue = newQueue;
    			}
    			rear = (rear+1)%capacity;
    			queue[rear] =x; 
    		}
  • pop 구현
  • template <class T> void Queue<T>::Pop() {// 큐로부터 원소를 삭제한다. if(isEmpty()) throw “Queue is empty. Cannot delete.”; front = (front+1)%capacity; queue[front].~T(); // T를 위한 파괴자 }

미로 maze

  • 1≤i≤m이고 1≤j≤p인 이차원 배열 maze[m][p]로 표현
  • 1 : 통로가 막혀 있음, 0 : 통과할 수 있음
  • 경계선에 있는 경우 : i ==1, i == m , j==1, j == p 인 경우
    • 경계 조건을 매번 검사하지 않기 위해 미로의 주위를 1로 둘러쌈
    • 배열은 maze[m+2][p+2]로 선언
  • 이동 방향 미리 정의하는 방법
  • 구현

maze.cpp

#include <iostream>
#include <stack>
using namespace std;
 
const int MAXSIZE = 100;
bool maze[MAXSIZE + 2][MAXSIZE + 2];
bool mark[MAXSIZE + 1][MAXSIZE + 1] = { 0 };
enum directions { N, NE, E, SE, S, SW, W, NW };
 
struct offsets {
	int a, b;
}
movea[8] = { -1,0, -1,1, 0,1, 1,1, 1,0, 1,-1, 0,-1, -1,-1 };
 
struct Items {
	Items(int xx = 0, int yy = 0, int dd = 0) : x(xx), y(yy), dir(dd) {}
	int x, y, dir; // dir은 다음에 방문 예정인 방향
};
 
template <class T>
ostream& operator<< (ostream& os, stack<T>& s) {
	// 스택의 내용을 역순으로 출력
	stack<T> s2;
 
  // 내용을 하나씩 꺼내 다른 임시 스택에 넣어 저장한 후,
	while (!s.empty()) { s2.push(s.top()); s.pop(); }
 
	// 그 임시 스택에서 하나씩 꺼내 출력
	while (!s2.empty()) {
		os << " -> " << s2.top();
		s.push(s2.top()); s2.pop();
	}
	return os;
}
 
ostream& operator<<(ostream& os, Items& item) {
	// 5개의 Items가 출력될 때마다 줄 바꾸기 위한 변수
	static int count = 0;
 
	os << "(" << item.x << "," << item.y << ")";
	count++;
 
	if ((count % 5) == 0) cout << endl;
	return os;
}
 
void Path(const int m, const int p) {
	mark[1][1] = 1;
	// C++ STD stack을 이용하기
	stack<Items> stack;
	// (1,1)에서 E방향부터(시계방향) 순차적으로 시도함
	Items temp(1, 1, E);
	stack.push(temp);
 
	while (!stack.empty()) {
		temp = stack.top(); stack.pop();
		// (i,j)부터 (g,h)로 이동한다
		int i = temp.x; int j = temp.y; int d = temp.dir;
		while (d < 8) {
			int g = i + movea[d].a; int h = j + movea[d].b;
 
			if ((g == m) && (h == p)) { // 출구에 도착하면
				// 경로를 출력한다.
				cout << stack;
				// 경로 상의 마지막 두 위치
				temp.x = i; temp.y = j; cout << "->" << temp;
				temp.x = m; temp.y = p; cout << "->" << temp << endl;
				return;
			}
 
			// 방문하지 않은 새로운 위치라면
			if ((!maze[g][h]) && (!mark[g][h])) {
				// 방문했다고 표시한다.
				mark[g][h] = 1;
				// 현 위치와 실패 시 다음에 시도할 방향을 저장한다.
				temp.x = i; temp.y = j; temp.dir = d + 1;
				stack.push(temp);
				// (g, h)로 이동한다. N방향부터 시계방향으로 시도하자.
				i = g; j = h; d = N;
			}
			else d++;
		}
	}
	cout << "No path in maze." << endl;
}
 
void getdata(istream& is, int& m, int& p) {
	// 자료화일을 읽어들여 maze에 저장한다
	is >> m >> p;
	for (int i = 0; i < m + 2; i++) { maze[i][0] = 1; maze[i][p + 1] = 1; }
	for (int j = 1; j <= p; j++) { maze[0][j] = 1; maze[m + 1][j] = 1; }
 
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= p; j++)
			is >> maze[i][j];
}
#include <iostream>
#include <fstream>
using namespace std;
 
void getdata(istream&, int&, int&);
void Path(int, int);
 
int main(int argc, char* argv[]) {
	int m, p; // m by p maze
 
	if (argc == 1)
		cerr << "Usage: " << argv[0] << " maze_data_file" << endl;
	else {
		ifstream is(argv[1]);
		if (!is) { cerr << argv[1] << " does not exist\\n"; exit(1); }
		cout << "For maze datafile (" << argv[1] << ")\\n";
		getdata(is, m, p); is.close();
		Path(m, p);
	}
}
 
12 15
0 1 0 0 0 1 1 0 0 0 1 1 1 1 1
1 0 0 0 1 1 0 1 1 1 0 0 1 1 1
0 1 1 0 0 0 0 1 1 1 1 0 0 1 1
1 1 0 1 1 1 1 0 1 1 0 1 1 0 0
1 1 0 1 0 0 1 0 1 1 1 1 1 1 1
0 0 1 1 0 1 1 1 0 1 0 0 1 0 1
0 0 1 1 0 1 1 1 0 1 0 0 1 0 1
0 1 1 1 1 0 0 1 1 1 1 1 1 1 1
0 0 1 1 0 1 1 0 1 1 1 1 1 0 1
1 1 0 0 0 1 1 0 1 1 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 1 1 1 1 0
0 1 0 0 1 1 1 1 1 0 1 1 1 1 0
 
For maze datafile (mazein.txt)
 -> (1,1) -> (2,2) -> (1,3) -> (1,4) -> (1,5)
 -> (2,4) -> (3,5) -> (3,4) -> (4,3) -> (5,3)
 -> (6,2) -> (7,2) -> (8,1) -> (9,2) -> (10,3)
 -> (10,4) -> (9,5) -> (8,6) -> (8,7) -> (9,8)
 -> (10,8) -> (11,9) -> (11,10) -> (10,11) -> (10,12)
 -> (10,13) -> (9,14) -> (10,15)->(11,15)->(12,15)

후위 표기식

  • 장점
    • 괄호가 불필요
    • 연산자의 우선 순위가 무의미
    • 계산 과정이 간단 (왼편에서 오른편으로 스캔)
  • 중위 표기식 → 후위 표기식 변환 알고리즘
    1. 식을 전부 괄호로 묶는다
    2. 이항 연산자들을 모두 자기 오른쪽 괄호로 이동시킨다.
    3. 괄호를 전부 삭제한다.
  • 연산자 우선 순위
    • 우선순위를 기반으로 스택에 push와 pop을 수행
    • ‘(‘ 의 우선순위가 문제임
    • 스택에 들어가기 전에는 가장 높은 우선순위의 연산자
    • 스택 속에 있을 때는 ‘)’가 나타날 때까지 낮은 우선순위의 연산자
    • so, 스택 top의 연산자의 isp가 새로운 연산자의 icp보다 산술적으로 작거나같을 때 스택에서 pop되어 출력 for (; isp(stack.Top()) <= icp(x); stack.Pop())
  • 예시
  • 구현
    • Expression e에 대한 NextToken(e)에서 unary – 와 binary –를 어떻게 구별하는가?
      • Infix Notation으로 된 Expression인 경우 Operand(피연산자) 후에 나온 –는 binary –이고, Operator(연산자) 후에 나온 –는 unary –이다. 단 맨 처음에 만난 –는 unary-로 간주한다.
      • Postfix Notation으로 된 Expression인 경우 입력자체가 binary –(-)와 unary –(-u)로 구별해야 함.

post.cpp

#include <iostream>
#include <stack>
#include "post.h"
using namespace std;
 
bool Token::operator==(char b) { return len == 1 && str[0] == b; }
bool Token::operator!=(char b) { return len != 1 || str[0] != b; }
 
Token::Token() {}
 
// 1-char token: type equals the token itself
Token::Token(char c) : len(1), type(c) {
	str = new char[1]; str[0] = c;
} // default type = c itself
 
// 2-char token(e.g. <=) & its type(e.g. LE)
Token::Token(char c, char c2, int ty) : len(2), type(ty) {
	str = new char[2]; str[0] = c; str[1] = c2;
}
 
//operand with its length & type(defaulted to ID)
Token::Token(char* arr, int l, int ty = ID) : len(l), type(ty) {
	str = new char[len + 1];
	for (int i = 0; i < len; i++) str[i] = arr[i];
	str[len] = '\\0';
 
	if (type == NUM) {
		ival = arr[0] - '0';
		for (int i = 1; i < len; i++) ival = ival * 10 + arr[i] - '0';
	}
	else if (type == ID) ival = 0;
	else throw "must be ID or NUM";
}
 
// 피연산자(ID 또는 NUM)인지 확인
bool Token::IsOperand() {
	return type == ID || type == NUM;
}
 
ostream& operator<<(ostream& os, Token t) {
	if (t.type == UMINUS) os << "-u";
	else if (t.type == NUM) os << t.ival;
	else for (int i = 0; i < t.len; i++) os << t.str[i];
	os << " ";
	return os;
}
 
bool GetID(Expression& e, Token& tok) {
	char arr[MAXLEN];  // ID 저장할 배열
	int idlen = 0;
	char c = e.str[e.pos];
 
	if (!(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')) return false;
 
	arr[idlen++] = c;
	e.pos++;
 
	while ((c = e.str[e.pos]) >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9') { 
		arr[idlen++] = c; e.pos++;
	}
	arr[idlen] = '\\0';
 
	tok = Token(arr, idlen, ID);
	return true;
}
 
bool GetInt(Expression& e, Token& tok) {
	char arr[MAXLEN];
	int idlen = 0;
	char c = e.str[e.pos];
 
	if (!(c >= '0' && c <= '9')) return false;
	arr[idlen++] = c;
	e.pos++;
 
	while ((c = e.str[e.pos]) >= '0' && c <= '9') { 
		arr[idlen++] = c; e.pos++;
	}
	arr[idlen] = '\\0';
 
	tok = Token(arr, idlen, NUM);
	return true;
}
 
void SkipBlanks(Expression& e) {
	char c;
	while (e.pos < e.len && ((c = e.str[e.pos]) == ' ' || c == '\\t'))
		e.pos++; 
}
 
// 두 글자 토큰들 처리: <= >= == != && || -u
bool TwoCharOp(Expression& e, Token& tok) {
	char c = e.str[e.pos]; char c2 = e.str[e.pos + 1];
	int op; // LE GE EQ NE AND OR UMINUS
	if (c == '<' && c2 == '=') op = LE;
	else if (c == '>' && c2 == '=') op = GE;
	else if (c == '=' && c2 == '=') op = EQ;
	else if (c == '!' && c2 == '=') op = NE;
	else if (c == '&' && c2 == '&') op = AND;
	else if (c == '|' && c2 == '|') op = OR;
	else if (c == '-' && c2 == 'u') op = UMINUS;
	else
		return false;
	tok = Token(c, c2, op); e.pos += 2;
	return true;
}
 
// 한 글자 토큰들 처리
bool OneCharOp(Expression& e, Token& tok) {
	char c = e.str[e.pos];
	if (c == '-' || c == '!' || c == '*' || c == '/' || c == '%' ||
		c == '+' || c == '<' || c == '>' || c == '(' || c == ')' || c == '=') {
		tok = Token(c); e.pos++;
		return true;
	}
	return false;
}
 
// 2nd arg=true for infix expression
Token NextToken(Expression& e, bool INFIX = true) {
	// 종전에 연산자 발견되었다고 가정
	static bool oprrFound = true; 
	Token tok;
 
	// 빈칸이 있다면 무시
	SkipBlanks(e);
 
	// 더 이상 남은 토큰이 없는 경우
	if (e.pos == e.len)
		{ if (INFIX) oprrFound = true; return Token('#'); }
 
	if (GetID(e, tok) || GetInt(e, tok)) 
		{ if (INFIX) oprrFound = false; return tok; }
 
	if (TwoCharOp(e, tok) || OneCharOp(e, tok)) {
		// 연산자 다음에 -가 나온 경우 -u로 바꿔라
		if (tok.type == '-' && INFIX && oprrFound)
			tok = Token('-', 'u', UMINUS);
 
		if (INFIX) oprrFound = true; return tok;
	}
	throw "Illegal Character Found";
}
 
// in-coming priority
int icp(Token& t) {
	int ty = t.type;
	int ty_num = -1;
 
	// ty가 '('면, 0, UMiNUS나 '!'면 1,'*'나 '/'나 '%'aus 2, '+'나 '-'면 3, '<'나 '>'나 LE나 GE면 4,
	//	EQ나 NE면 5, AND면 6, OR이면 7, '='이면 8,'#'면 9를 return 한다.
	if (ty == '(') ty_num = 0;
	else if (ty == UMINUS || ty == '!') ty_num = 1;
	else if (ty == '*' || ty == '/' || ty == '%') ty_num = 2;
	else if (ty == '+' || ty == '-') ty_num = 3;
	else if (ty == '<' || ty == '>' || ty == LE || ty == GE) ty_num = 4;
	else if (ty == EQ || ty == NE) ty_num = 5;
	else if (ty == AND) ty_num = 6;
	else if (ty == OR) ty_num = 7;
	else if (ty == '=') ty_num = 8;
	else if (ty == '#') ty_num = 9;
	else ty_num = -1;
 
	return ty_num;
}
 
//in-stack priority
int isp(Token& t) { 
	int ty = t.type;
	int ty_num = -1;
 
	// icp에서 (랑 #만 바뀜
	if (ty == '(') ty_num = 9;
	else if (ty == UMINUS || ty == '!') ty_num = 1;
	else if (ty == '*' || ty == '/' || ty == '%') ty_num = 2;
	else if (ty == '+' || ty == '-') ty_num = 3;
	else if (ty == '<' || ty == '>' || ty == LE || ty == GE) ty_num = 4;
	else if (ty == EQ || ty == NE) ty_num = 5;
	else if (ty == AND) ty_num = 6;
	else if (ty == OR) ty_num = 7;
	else if (ty == '=') ty_num = 8;
	else if (ty == '#') ty_num = 10;
	else ty_num = -1;
 
	return ty_num;
}
 
// 중위 표기식 e의 후위 표기식을 출력한다.
void Postfix(Expression e) {
	// 스택 초기화
	stack<Token> stack;
	// End Of String 표시
	stack.push('#');
 
	for (Token x = NextToken(e); x != '#'; x = NextToken(e))
		if (x.IsOperand()) cout << x;
		else if (x == ')') {
			// '('까지 스택에서 꺼낸다.
			for (; stack.top() != '('; stack.pop())
				cout << stack.top();
			// 'C'를 제거한다.
			stack.pop();
		} else { // x가 연산자일 떄
			for (; isp(stack.top()) <= icp(x); stack.pop()) {
				// 예외처리: a = b = 0 같은 우결합 연산자에선
				// 나중에 나온 = 이 우선순위가 높음.
				if (x == '=' && stack.top() == '=') break;
				cout << stack.top();
			}
			stack.push(x);
		}
 
	// 마지막 '#'의 출력은 생략한다.
	while (stack.top() != '#') { cout << stack.top(); stack.pop(); }
	stack.pop();
 
	cout << endl;
 
}

post.h

#ifndef POST_H
#define POST_H
// token types for non one-char tokens
#define ID 257
#define NUM 258
 
#define EQ 259
#define NE 260
#define GE 261
#define LE 262
#define AND 263
#define OR 264
#define UMINUS 265
#define MAXLEN 80
 
struct Expression {
	Expression(char* s) : str(s), pos(0) { for (len = 0; str[len] != '\\0'; len++); }
	char* str;
	int pos;
	int len;
};
struct Token {
	bool operator==(char);
	bool operator!=(char);
	Token();
	Token(char); // 1-char token: type equals the token itself
	Token(char, char, int); // 2-char token(e.g. <=) & its type(e.g. LE)
	Token(char*, int, int); //operand with its length & type(defaulted to ID)
	bool IsOperand(); // true if the token type is ID or NUM
 
	int type; // ascii code for 1-char op; predefined for other tokens
	char* str; // token value
	int len; // length of str
	int ival; // used to store an integer for type NUM; init to 0 for ID
};
 
using namespace std;
ostream& operator<<(ostream& os, Token t);
Token NextToken(Expression&, bool); // 2nd arg=true for infix expression
#endif
A * B * C
-A + B - C + D
A * -B + C
(A + B) * D + E / (F + A * D) + C
 
A B * C * 
A -u B + C - D + 
A B -u * C + 
A B + D * E F A D * + / + C +
A * B * C
-A + B - C + D
A * -B + C
(A + B) * D + E / (F + A * D) + C
 
A B * C * 
A -u B + C - D + 
A B -u * C + 
A B + D * E F A D * + / + C +
A && B||C||!(E>F)
!(A&&!((B<C)||(C>D)))||(C<E)
 
A B && C || E F > ! || 
A B C < C D > || ! && ! C E < ||
34 * 56 + 11 / 2
1 + 2 * 3 + - 4 * 2s
 
34 56 * 11 2 / + 
1 2 3 * + 4 -u 2 s * +
33 + 55 * 2
an77 = 2 + 7 * 5
b = 2
an77 + b * 2
a + 5
 
33 55 2 * + 
an77 2 7 5 * + = 
b 2 = 
an77 b 2 * + 
a 5 +

eval.cpp

#include <iostream>
#include <stack>
#include "post.h"
using namespace std;
 
int GetVal(Token& opnd) {
	if (opnd.type == NUM) return opnd.ival;
	return 0; // ID인 경우는 0을 return
}
 
// UMINUS와 ‘!’의 두가지 경우만 처리함
Token UnaryOp(int op, Token& x) {
	if (!x.IsOperand()) throw "Operand Only for Unary Operator";
	Token tmp; tmp.type = NUM;
 
	if (op == UMINUS) tmp.ival = -GetVal(x);
	else if (op == '!') tmp.ival = !GetVal(x);
	else throw "Invalid unary operator";
 
	return tmp;
}
 
Token BinaryOp(int op, Token& left, Token& right) {
	if (!left.IsOperand() || !right.IsOperand())
		throw "Two Operands required for Binary Operation";
 
	Token tmp; tmp.type = NUM;
	int val1 = GetVal(left), val2 = GetVal(right);
 
	if (op == '+') tmp.ival = val1 + val2;
	else if (op == '-') tmp.ival = val1 - val2;
	else if (op == '*') tmp.ival = val1 * val2;
	else if (op == '/') tmp.ival = val1 / val2;
	else if (op == '%') tmp.ival = val1 % val2;
	else if (op == '<') tmp.ival = val1 < val2;
	else if (op == '>') tmp.ival = val1 > val2;
	else if (op == GE) tmp.ival = val1 >= val2;
	else if (op == LE) tmp.ival = val1 <= val2;
	else if (op == EQ) tmp.ival = val1 == val2;
	else if (op == NE) tmp.ival = val1 != val2;
	else if (op == NE) tmp.ival = val1 && val2;
	else if (op == NE) tmp.ival = val1 || val2;
	else if (op == '=') throw "Assignment Not Yet Implemented";
	else throw "No such binary operator";
	return tmp;
}
 
// 스택의 top에 있는 것을 꺼내어 return한다.
Token DeleteFromStack(stack<Token>& stack) {
	if (stack.empty()) throw "Trying to pop from an empty stack";
 
	Token tmp = stack.top();
	stack.pop();
	return tmp;
}
 
// postfix 표현식을 입력으로 받아 그 값을 계산한다.
void Eval(Expression e) {
	stack<Token> stack;
	Token opnd1, opnd2;
	for (Token x = NextToken(e, false); x != '#'; x = NextToken(e, false))
		if (x.IsOperand()) stack.push(x);
		else { // x is an operator
			// unary operator
			if (x.type == UMINUS || x.type == '!') {
				opnd1 = DeleteFromStack(stack);
				stack.push(UnaryOp(x.type, opnd1));
			}
			else { // binary operator
				opnd1 = DeleteFromStack(stack);
				opnd2 = DeleteFromStack(stack);
				stack.push(BinaryOp(x.type, opnd2, opnd1));
			}
		}
 
	// 최종 계산 결과 출력
	cout << DeleteFromStack(stack) << endl;
}

posteval.cpp

#include <iostream>
#include "post.h"
using namespace std;
void Eval(Expression);
int main(void)
{
	char line[MAXLEN];
	while (cin.getline(line, MAXLEN)) {
		Expression e(line); // Assume postfix notation
 
		try {
			Eval(e);
		} catch (char const* msg) {
			cerr << "Exception: " << msg << endl;
		}
	}
}
 
34 56 * 11 2 / + 
1 2 3 * + 4 -u 2 * + 
33 55 2 * +
 
1909 
-1 
143
저작자표시 비영리 동일조건

'[전공] > [자료구조]' 카테고리의 다른 글

[C++ 자료구조론] 2장 배열  (1) 2022.10.30
[C++ 자료구조론] 1장 기본 개념  (1) 2022.10.30

'[전공]/[자료구조]'의 다른글

  • 현재글[C++ 자료구조론] 3장 스택과 큐

관련글

댓글

티스토리툴바