CH 06 Review

Stack

문제

수식을 표현하는 데 연산자 우선 순위가 없다고 가정하자. 예를 들어, 연산자 우선 순위가 없으므로 "3 + 4 * 2 = 7 * 2 = 14"가 된다. 연산자 우선 순위가 없는 infix 수식을 postfix 수식으로 변환하는 프로그램을 작성하고자 한다. infix 수식은 피연산자 사이에 연산자가 존재하는 수식을 의미하고, postfix 수식은 피연산자들 뒤에 연산자가 존재하는 수식을 말한다. 따라서, 작성하고자 하는 프로그램은 "3 + 4 * 2 - 7"을 "34 + 2 * 7 -"로 변환한다. 빈 부분을 채우시오.

int main() {
	string in;
	StackType<char> st;
	int noperand = 0;
	getline(cin, in);
	for (int i = 0; i < in.length(); i++) {
		string s = "";
		if (isdigit(in[i])) {
			while (isdigit(in[i])) {
				s += in[i];
				++i;
			}
			--i;
			if (noperand == 0) {
				cout << s << "";
				++noperand;
			}
			else {
				cout << s << "";
				cout << _____(a)_____ << "";
				_____(b)_____
			}
		}
		else if (in[i] == '+' || in[i] == '-' || in[i] == '*' || in[i] == '/')
			_____(c)_____
	}
	cout << '\n';
}

정답

#include "Stack.h"
#include <iostream>
#include <string>

using namespace std;

int main() {
	string in;
	StackType<char> st;
	int noperand = 0;
	getline(cin, in);
	for (int i = 0; i < in.length(); i++) {
		string s = "";
		if (isdigit(in[i])) {
			while (isdigit(in[i])) {
				s += in[i];
				++i;
			}
			--i;
			if (noperand == 0) {
				cout << s << "";
				++noperand;
			}
			else {
				cout << s << "";
				cout << st.Top() << "";
				st.Pop();
			}
		}
		else if (in[i] == '+' || in[i] == '-' || in[i] == '*' || in[i] == '/')
			st.Push(in[i]);
	}
	cout << '\n';
}

Stack and Queue

문제

아래 프로그램의 출력 결과를 쓰시오. 단, QueueType::GetRear()는 queue에서 가장 오래된 원소를 리턴한다고 가정하시오.

#include "Stack.h"
#include "Queue.h"
#include <iostream>

int main() {
	QueType q;
	StackType<int> s;
	s.Push(5);
	s.Push(6);
	s.Push(s.Top());
	s.Push(7);
	q.Enqueue(s.Top());
	s.Pop();
	q.Enqueue(5);
	q.Enqueue(6);
	std::cout << q.GetRear() << std::endl;
	int i = 0;
	q.Dequeue(i);
	s.Push(i);
	std::cout << s.Top() << std::endl;
	s.Pop();
	s.Pop();
	std::cout << s.Top();
}

정답

6
7
6

Linked-list UnsortedType

문제

주어진 코드는 UnsortedType linked list의 DeleteItem 함수이다. 이 코드에서 존재하지 않는 item을 삭제하려는 경우 문제가 발생한다. 문제를 해결하도록 코드를 고치시오.

template<class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item) {
	NodeType<ItemType>* location;
	NodeType<ItemType>* tempLocation;
	location = listData;
	if (location->info == item) { // 처음에 item 존재
		tempLocation = location;
		listData = location->next;
	}
	else {// 중간에 item 존재
		while ((location->next)->info != item)
			location = location->next;
		tempLocation = location->next;
		location->next = (location->next)->next;
	}
	delete tempLocation;
	length--;
}

정답

template<class ItemType>
void UnsortedType<ItemType>::DeleteItem2(ItemType& item) {
	NodeType<ItemType>* location = listData;
	NodeType<ItemType>* predLoc;
	NodeType<ItemType>* tempLocation;

	bool stop = false;

	while (!stop) {
		if (location == NULL)
			break;
		else {
			if (location->info == item) {
				tempLocation = location;

				if (predLoc == NULL) {
					location = location->next;
					listData = location;
				}

				else {
					if (location->next == NULL) 
						stop = true;
					predLoc = location;
					location = location->next;
				}

				//한 번만 할 경우
				// stop = true;
				delete tempLocation;
				length--;
			}
			else {
				predLoc = location;
				location = location->next;
			}
		}
	}
}

UnsortedType

문제

UnsortedType의 list에서 중복된 원소가 있는지 확인하는 멤버 함수bool hasDuplicatedElements()를 구현하고자 한다. 빈 곳을 채우시오.

bool UnsortedType::hasDuplicatedElements() {
    for (int i = 0; i < length; i++) {
        for (_____(a)_____) {
            if (_____(b)_____)
                return true;
        }
    }
    return false;
}

정답

bool UnsortedType::hasDuplicatedElements() {
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; i++) {
            if (info[i].ComparedTo(info[j]) == EQUAL)
                return true;
        }
    }
    return false;
}