4th HomeWork Guide (ver2.0)

Presentation on theme: "4th HomeWork Guide (ver2.0)"— Presentation transcript:

1 4th HomeWork Guide (ver2.0)
Internet Computing KUT Youn-Hee Han

2 1. Deque의 구현 A Double ended queue Has operations that
Add, remove, or retrieve entries at both its front and back Combines and expands the operations of queue and stack d.printDeque() d.isEmpty() Data Structure

3 1. Deque의 구현 Interface (Deque.h) class Deque { public:
class Node{ // Deque 의 내부노드 클래스 - doubly linked list int data; Node *prev; Node *next; Node(){ prev = next = NULL; } }; Deque(); // 생성자 ~Deque(); // 소멸자 void addToFront(int data); // 맨앞에 삽입 void addToBack(int data); // 맨뒤에 삽입 void removeFront(); // 맨앞 삭제(반환x) void removeBack(); // 맨뒤 삭제(반환x) int getFront(); // 맨앞 데이터 반환 int getBack(); // 맨뒤 데이터 반환 void printDeque(); // Deque 내용 출력 bool isEmpty(); // 비었는지 검사하는 함수 private: Node *front; // front Node *rear; // rear int count; // 갯수 Data Structure

4 1. Deque의 구현 Implementation (Deque.cpp) #include <iostream>
#include “Deque.h" using namespace std; Deque::Deque() { // 생성자 front = NULL; rear = NULL; count = 0; } Deque::~Deque() { // 소멸자 - 모든 노드 삭제. for (int i=0; i<count; i++) removeBack(); void Deque::addToFront(int data) { // 맨앞에 삽입 Node *newNode = new Node; // 새로운 노드 할당 - prev,next 는 null 로 초기화 된다. newNode->data = data; if ( IsEmpty() ) front = rear = newNode; else { newNode->next = front; front->prev = newNode; front = newNode; count++; // 삽입 후 카운터 증가 Data Structure

5 1. Deque의 구현 문제 1 – 30점 만점 addToFront 외에 나머지 addToBack(int data), removeFront, removeBack() getFront(), getBack(), printDeque(), isEmpty()를 구현하시오. 활용 예 #include <iostream> using namespace std; #include "deque.h" void main() { Deque queue; queue.addToFront(3); queue.PrintDeque(); queue.addToFront(5); queue.PrintDeque(); queue.removeFront(); queue.PrintDeque(); queue.addToBack(7); queue.PrintDeque(); queue.removeBack(); queue.PrintDeque(); queue.addFront(9); queue.PrintDeque(); queue.addBack(7); queue.PrintDeque(); queue.addFront(3); queue.PrintDeque(); } Data Structure

6 2. Calculator의 구현 Let's convert an infix string to a postfix string.
Postfix preserves the order of operands, so an operand can be appended to postfix as soon as that operand is encountered in infix. The operands for ‘-’ are not yet in postfix, so ‘-’ must be temporarily saved somewhere. (stack) INFIX x – y * z INFIX POSTFIX x – y * z x INFIX POSTFIX x – y * z x – Data Structure

7 2. Calculator의 구현 Next operand is appended to postfix.
The operands for '*' must be pushed to the stack, because '*' has greater precedence than top operator, '-', of the stack. Next operand is appended to postfix INFIX POSTFIX x – y * z xy – INFIX POSTFIX x – y * z xy * – INFIX POSTFIX x – y * z xyz * – Data Structure

8 2. Calculator의 구현 At the end of infix expression, pop the all data from the stack. How about the followings? Until now, do you understand…? INFIX POSTFIX x – y * z xyz*- INFIX x * y - z INFIX POSTFIX x * y - z xy * Data Structure

9 2. Calculator의 구현 The top operator '*‘ stored in the stack must be popped and then the operator ‘-’ should be pushed, because ‘-' has lower precedence than the top operator, ‘*', of the stack. Next operand is appended to postfix. At the end of infix expression, pop the all data from the stack. INFIX POSTFIX x * y - z xy* – INFIX POSTFIX x * y - z xy*z – INFIX POSTFIX x * y - z xy*z- Data Structure

10 2. Calculator의 구현 a + b * c / d - e abc*d/+e – 알고리즘 Exercise
피연산자를 만나면 그대로 출력 연산자를 만나면 Stack Top에 있는 것보다 새로 들어오려는 연산자의 우선순위가 높을 경우 그 새로운 연산자를 Push Stack Top에 있는 것보다 새로 들어오려는 연산자의 우선순위가 낮거나 같을 경우 Stack Top의 것을 Pop 하여 출력한 후 새로운 연산자를 Push 더 이상 수식표현이 없으면 스택 내의 모든 연산자를 Pop하여 출력 Exercise INFIX POSTFIX a + b * c / d - e abc*d/+e – Data Structure

11 2. Calculator의 구현 How about this?
The operator ‘(‘ is just pushed to the stack. Next operand is appended to postfix. INFIX (x – y) * z INFIX POSTFIX (x – y) * z ( INFIX POSTFIX (x – y) * z x ( Data Structure

12 2. Calculator의 구현 In stack top, there is ‘(‘. At this case, just push ‘-’ Next operand is appended to postfix. The operator ‘)’ allows to pop all elements above the operator ‘(‘ in the stack. And then, both ‘(‘ and ‘)’ are just ignored. INFIX POSTFIX (x – y) * z x – ( INFIX POSTFIX (x – y) * z xy – ( INFIX POSTFIX (x – y) * z xy- Data Structure

13 2. Calculator의 구현 Operator is pushed to the stack
Next operand is appended to postfix. At the end of infix expression, pop the all data from the stack. INFIX POSTFIX (x – y) * z xy- * INFIX POSTFIX (x – y) * z xy-z * INFIX POSTFIX (x – y) * z xy-z* Data Structure

14 2. Calculator의 구현 x * (y + z – (a / b + c) * d) / e 괄호를 고려한 최종 알고리즘
Case 1 - 피연산자를 만나면 그대로 출력 Case 2 - 연산자를 만나면 Stack Top에 ‘(‘이 있는 경우 : 현재 연산자를 단순히 Stack에 Push한다. Stack Top에 있는 것보다 현재 연산자의 우선순위가 높을 경우 : 현재 연산자를 단순히 Stack에 Push한다. Stack Top에 있는 것보다 현재 연산자의 우선순위가 낮거나 같을 경우 : Stack Top의 것을 Pop 하여 출력한 후 현재 연산자를 Stack에 Push한다. Case 3 – 괄호를 만나면 왼쪽 괄호 ‘(’인 경우 : 단순히 Stack에 ‘(‘을 Push 한다. 오른쪽 괄호 ‘)’인 경우 : 스택에서 왼쪽 괄호와 그 위에 쌓여있는 연산자를 모두 Pop하여 출력한다. 더 이상 수식표현이 없으면 스택 내의 모든 연산자를 Pop하여 출력 Exercise INFIX POSTFIX x * (y + z – (a / b + c) * d) / e Data Structure

15 2. Calculator의 구현 Left-associative와 Right-associative
4 ^ 2 ^ 3 = 4 ^ (2 ^ 3) = 4 ^ 6 = (2 + 3) + 5 = 5 + 5 10 % 7 % 2 = (10 % 7) % 2 = 3 % 2 = 1 Data Structure

16 2. Calculator의 구현 문제 2. Calculator의 구현 – 1/3 실행 예
> (3 + 4)^2 - 3 * (2 + 3) 3 4+2^3 2 3+*- 34 > 3 * * 6 3 4*5 6*- -18.0 > 100 / 2 ^ 2 ^/ 25 > 2^2^3 2 2 3^^ 256 > q 괄호 처리를 포함한 Infix  Postfix 변환과 Evaluation 결과를 보여주면 기본 점수 30점 Data Structure

17 2. Calculator의 구현 문제 2. Calculator의 구현 – 2/3 실행 예
> (1 + 3 * 33 괄호 매칭 오류 > 3 & * 6 허용하지 않은 기호 기입 오류 > ^ 2 연속된 Operand 기입 오류 > * 2 연속된 Operator 기입 오류 > * 수식 자체 오류 > q 왼쪽과 같은 오류 처리를 수행하면 추가 점수 20점 Data Structure

18 2. Calculator의 구현 문제 2. Calculator의 구현 – 3/3 Due Date 실행 예
문제 2의 총 점수 기본 점수 30 + 오류 처리 20 + 실수 처리 10 + 음수 처리 10 = 70 점 만점 주의: Stack 자료구조 사용하지 말고 이번 숙제에서 개발한 Deque를 Stack 처럼 사용할 것. Due Date 2007년 5월 15일 23시 59분 59초 > 32.5 왼쪽과 같이 실수 (Real Number)처리를 하면 추가 점수 10점 > ((-20.2) ) * 1 (-20.2) * -8.9 왼쪽과 같이 음수 처리를 하면 추가 점수 10점 Data Structure