후위표기법으로 계산기 만들기 계산기 관련 외주가 들어와서 해보던 중, 예전에 배웠던 후위표기법을 사용해야했다. 그런데 기억이 안나서 검색 없이 혼자 구현하려다 보니 너무 어려웠다... 검색해보니까 stack을 이용해서 후위표기법을 만드는 간단한 방법이 나와있어서 까먹지 않기 위해 기록한다. 후위 표기법 수식 트리 후위 표기법이란 계산식에서 계산을 위해 사용하는 표기법이다. 예제와 함께 살펴보자. 수식 : 9x3+1-3%3 수식이 주어졌을 때 비연산자와 연산자로 나눈 후, 각 항목을 하나의 노드라고 생각하면 트리 형태로 만들 수 있다. 이러한 트리는 수식을 트리라는 자료구조로 만든 것이니 수식트리, 즉 Expression Tree라고 불린다. 트리 순회와 표기법 트리를 순회하는 방식에는 prefix(전위)..

서론 자료구조 자료구조는 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조를 말한다. 프로그램은 자료구조와 알고리즘으로 이루어져있기 때문에, 자료구조는 반드시 공부해야하는 분야이다. 자료구조는 먼저 단순 자료구조와 복합 자료구조로 구분되고, 복합 자료구조에는 선형 구조와 비선형 구조가 있다. 순차적으로 살펴보자. 배열, 문자열 연결 리스트 스택, 큐, 덱 그래프 트리 힙 구조체

탑 https://programmers.co.kr/learn/courses/30/lessons/42588?language=cpp 코드 #include #include #include using namespace std; vector solution(vector heights) { int heights_len = heights.size(); vector answer(heights_len); stack stk; // index, key for (int i = heights_len - 1; i>0; i--) { if (heights[i - 1] > heights[i]) { answer[i] = i; // stack while (stk.size() != 0) { auto tmp = stk.top(); if (h..

스택 특징 용도 연산 삽입 삭제 접근 구현 큐 용도 종류 연산 삽입 삭제 접근 구현 우선순위 큐 덱 용도 구현 스택 스택은 LIFO(Last-In First-Out), 즉 후입선출의 자료구조이다. 구조는 다음과 같은 형태이며, 접시처럼 쌓여서 이후에 삽입된 데이터가 먼저 빠져나가도록 되어있다. top 변수는 가장 최근에 들어온 요소를 가리키며 스택이 비어있으면 -1이다. 특징 LIFO 내부 요소를 확인할 방법이 pop 말고는 없다. 용도 입력의 역순이 필요할 때 스택을 주로 사용하며, 함수의 호출에서 복귀 주소를 기억하기 위해서 시스템 스택이 사용되기도 한다. 또한 괄호 검사, 계산기, 미로 탐색 등의 경우에 스택이 유용하게 사용된다. 계산기에서 중위 표기식(infix)을 후위 표기식(postfix)으로..