※ 연산자 우선순위 : ( ) stack에 존재하는 연산자 pop한 후, 다음 처리 연산자 push 왼쪽 괄호 -> 오른쪽 괄호 만날때 까지, 왼쪽 괄호위에 push된 연산자 pop int priority(char op) { // 연산자 우선순위 switch (op) { case '(': case')': return 1; case '+': case'-': return 2; case '*': case'/': return 3; } return -1; } void infix_to_postfix(const char* str) { stack s; init_stack(..

알고리즘 - 후위 표기 수식 str이 존재 str에서 피연산자(숫자)를 만나면 stack에 push str에서 연산자를 만나면 stack에서 pop2번 (숫자1, 숫자2) pop한 숫자 2개를 연산자로 계산 계산결과를 stack에 다시 push int postfixCalc(const char*str) { // 후위 표기 수식을 계산한 값 리턴 stack s; init_stack(&s); char ch; // 후위 표기 수식 str에서 하나하나 추출하는 자료형 int value = 0; // str에서 추출한 숫자가 문자형일때 '1', '2' 숫자로 변환 1, 2 해서 저장하는 자료형 int pop1, pop2; // pop1 = 스택에서 pop한 첫번째 값, pop2 = 스택에서 pop한 두번째 값 in..

수식 표기법 - 전위(prefix) : 연산자(+,-,/,*)를 먼저 표시 - 중위(infix) : 보통 우리가 쓰는 수식 표기법 - 후위(postfix) : 피연산자를 먼저 표시 ① 중위 → 후위 : 8/2-3+3×2 1. 연산자 우선순위에 맞게 괄호로 묶기 (1) (8/2) (2) (3×2) (3) ((8/2)-3) (4) (((8/2)-3) + (3×2)) ≫ (((8/2)-3) + (3×2)) 2. 연산자를 괄호 우측으로 옮기기 (괄호로 적게 묶인 연산자부터 가장 바깥 괄호로) ≫ (((82)/3)-(32)×)+ 3. 괄호 없애기 ≫ 82/3-32×+ ② 중위 → 전위 : 8/2-3+3×2 1. 연산자 우선순위에 맞게 괄호로 묶기 (1) (8/2) (2) (3×2) (3) ((8/2)-3) (4)..

괄호 검사 - 대괄호 [], 중괄호 {}, 소괄호 ()가 서로 짝이 맞는지 검사 왼쪽 괄호 개수 = 오른쪽 괄호 개수 같은 종류의 괄호이면, 왼쪽 괄호가 더 먼저 나와야 한다 서로 다른 종류의 괄호면 쌍을 이루면 안된다 알고리즘 - 하나의 문자열 str이 존재 str안에 왼쪽 괄호 [, {, (는 push를 통해서 stack에 저장 오른쪽 괄호 ], }, )를 만나면 stack에 저장된 왼쪽 괄호를 pop시켜서 서로 짝이 맞는지 확인 오른쪽 괄호를 만났는데 stack이 비어있거나, pop한 문자가 다르면 검사 실패 모든 괄호 검사가 끝난 다음, stack을 봤는데 stack이 안비워져 있다면 검사 실패 int check_bracket(const char* str) { stack s; char ch, po..

스택이란? "LIFO 구조" : Last-In First-Out 프링글스 과자라고 생각하면 된다 프링글스는 제조 과정에서 과자들을 차례대로 통에 넣어준다 당연히 프링글스를 사먹는 사람들은 일반적으로 제조과정에서 마지막에 넣은 과자를 먼저 먹게된다 이처럼 스택은 몇몇 요소들을 넣으면 가장 나중에 넣은 요소들부터 차레대로 pop이 되는 구조이다 스택 ADT (추상 자료형) - n개의 element형의 요소들의 선형 리스트 boolean is_full(stack *s) 스택 포화 상태 검출 함수 boolean is_empty(stack *s) 스택 공백 상태 검출 함수 void push(stack *s, element item) 스택 s에 item을 삽입 element pop(stack *s) 스택 s의 가장..

하노이 탑 (The Tower of Hanoi) - 원판은 1번에 1개씩만 옮겨야 한다 - 맨 위에 있는 원판만 이동 가능 - 작은 원판 위에 큰 원판을 올려 놓을 수 없다 n개가 존재하고 막대가 3개 (A, B, C)일 경우 n-1개의 원판을 B로 옮기고 맨 밑에 1개의 원판을 C로 옮기고 B에 있는 n-1개의 원판을 C로 옮기면 된다 ※ 코드 구현 #include void hanoi(int n, char from, char tmp, char to) { /* n = 원판의 개수 from = 시작 지점 tmp = 경유 지점 to = 도착 지점 */ /* 1. n-1개의 원판을 경유 지점에 잠시 놓는다 (여기서의 경유 지점 = to) 2. 맨밑에 있는 1개의 원판을 최종 도착지점에 옮긴다 (여기서의 경유 ..