C 자료구조/3. 스택( Stack )
-
스택의 활용 - 미로 탐색C 자료구조/3. 스택( Stack ) 2020. 9. 16. 18:13
참고 문헌 설명 미로에서 탈출하기 위해서는 미로를 체계적으로 탐색하여야 할 것이다. 출구를 찾는 기본적인 방법은 시행 착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고 안되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 안 될 경우에 다른 경로를 선택해야 한다는 것으로 가능한 경로들이 어딘가에 저장되어 있어야 한다. 그리고, 현재 위치에서 가능한 경로 중에서 가장 가까운 경로이면 좋을 것이다. 따라서 가능한 경로들이 저장되는데 그 중에서 가장 최근에 저장한 경로가 쉽게 추출되는 자료구조를 사용해야 할 것이다. 따라서 결론은 "스택"이 후보가 된다. 현재 위치에서 갈 수 있는 칸들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 가장 가깝고, 아직 가보지 않은 칸으로 다시 돌아가서 새로..
-
스택의 활용 - 스택 계산기 (괄호 포함)C 자료구조/3. 스택( Stack ) 2020. 6. 24. 11:25
아래의 글에서 괄호를 포함한 중위 표기법을 후위 표기법으로 변경해 봤다. designatedroom87.tistory.com/25?category=868809 스택의 활용 - 중위 표기법에서 후위 표기법으로 변환(괄호 포함) 괄호를 포함한 중위 표기법을 후위 표기법으로 변경하는 알고리즘 괄호가 있는 중위 표기법을 후위 표기법으로 변경하는 함수 메인 함수 프로그램 실행 결과 아래는 소스 파일 designatedroom87.tistory.com 그러면, 후위 표기법을 계산하면 되는데, 이는 앞의 스택 계산기의 내용과 같다. 이미 후위 표기법으로 만들었기 때문에, 후위 표기법의 계산은 앞의 내용과 동일하다. 그리고, 스택에 저장할 데이터는 float 형이다. 내용은 같지만, 그래도 함수를 다시 보도록 하자. ..
-
스택의 활용 - 스택 계산기 (괄호 제외)C 자료구조/3. 스택( Stack ) 2020. 6. 24. 10:18
아래에서 중위 표기법을 후위 표기법으로 변경하는 방법을 알아봤다. designatedroom87.tistory.com/23?category=868809 스택의 활용 - 중위 표기법에서 후위 표기법으로 변환(괄호 제외) 중위 표기법에서 후위 표기식으로 바꾸는 알고리즘. 1. 중위 표기법 배열을 왼쪽에서 오른쪽으로 탐색. 2. 만약 피 연산자(숫자)를 만나게 되면, 바로 후위 표기 배열에 저장. 3. 연산자를 만나게 designatedroom87.tistory.com 이번에는 이 후위 표기법으로 가지고 계산기를 만들어 보자. 스택에 저장할 테이터의 타입은 float이다. 계산 알고리즘 후위표기법 배열을 왼쪽에서 오른쪽으로 탐색하면서 피 연산자(숫자)이면 스택에 저장. 연산자이면 숫자를 스택에서 꺼내 연산을 ..
-
스택의 활용 - 중위 표기법에서 후위 표기법으로 변환(괄호 제외)C 자료구조/3. 스택( Stack ) 2020. 6. 24. 09:44
중위 표기법에서 후위 표기식으로 바꾸는 알고리즘. 1. 중위 표기법 배열을 왼쪽에서 오른쪽으로 탐색. 2. 만약 피 연산자(숫자)를 만나게 되면, 바로 후위 표기 배열에 저장. 3. 연산자를 만나게 되면, 연산자 우선 순위를 판단하여야 함. 3 - (1). 스택에 존재하는 연산자가 현재 처리중인 연산자보다 우선 순위가 높으면, 일단 스택에 있는 연산자들을 먼저 후위배열에 저장하고 나서 나중에, 현재 처리중인 연산자를 스택에 넣어야 한다. 3 - (2). 만약 우선 순위가 같다면, 일단 스택 상단의 요소를 꺼내 후위배열에 저장하고 나서 현재 처리중인 연산자를 스택에 저장 중위 표기법은 후위 표기법으로 변경하는 함수 메인 함수 프로그램 실행 결과 아래는 소스 파일 아래는 스택 라이브러리를 이용한 중위 표기..
-
Stack의 활용 - 문자열에 들어있는 괄호의 짝 검사C 자료구조/3. 스택( Stack ) 2020. 6. 22. 22:57
프로그램에서는 여러 가지 타입의 괄호들이 같은 타입으로 쌍으로 존재하여야 한다. 프로그램에서는 대괄호, 중괄호, 소괄호 등이 사용된다. 괄호의 검사 조건은 다음의 3가지 이다. 조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건 2 : 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건 3 : 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다. 에러의 종류를 살펴보자. { A[ ( i + 1 ) ] }
-
1. Stack 직접 만들기C 자료구조/3. 스택( Stack ) 2020. 6. 10. 12:01
우리는 아래의 포스트에서 라이브러리로 구현되어 있는 스택을 사용해봤다. designatedroom87.tistory.com/7?category=868809 0. stack library 맛 보기 제공하는 스택을 쓰기 위해서는 C++의 template에 대한 이해가 필요. main.cpp 프로그램 결과 designatedroom87.tistory.com 스택은 라이브러리로 구현이 되있기는하나, 속도가 느리며, 입맛대로 바꿀수 없다. 그렇기 때문에, 직접 만들어 봐야 한다. 스택의 기본적 모양은 아래와 같다. 아래의 Top은 연결 리스트에서의 Head와 역할이 같다. 스택은 나중에 들어간 데이터가 가장 맨 위에 위치한다. 여러개의 함수 및 구조체를 정의함에 따라 프로그램이 길어져 파일분할 합니다. 프로그램 ..