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()は、キュー内で最も古い要素を返します.

#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 linklistのDeleteItem関数です.このコードに存在しないアイテムを削除しようとすると、問題が発生します.問題を解決するためにコードを変更してください.

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

質問する

メンバー関数boolhasDuplicateElements()を実装するには、UnsortedTypeのリストで重複する要素があるかどうかを確認します.空き地を埋める.

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;
}