C/C++에서는 중괄호를 사용하여 소스 코드를 묶는다. 소스 코드에 여는 괄호가 두 번 나왔다면 닫는 괄호도 반드시 두 번 나와야 한다. 실제로 이러한 문법 검증 작업은 컴파일에 의해 이루어지며 이를 위해 컴파일러는 스택을 사용한다. 다음은 유사코드로 작성한 괄호의 매칭이다. Matched = TRUE; //매칭 상태를 표시하는 변수 초기화 while(index

주어진 문자열이 들어오는 대로 스택에 푸시했다고 가정하면 마지막 문자는 스택 탑에 위치하게 된다. 따라서 문자열을 역순으로 표시하려면 순차적으로 팝을 가하면 된다.

10진수 26을 2 진수로 변환한다고 해보자. 먼저, 26을 2로 나누었을때, 나머지인 0을 push 한다. 그 몫인 13을 다시 2로 나누고, 나머지인 1을 push한다. 다시 그 몫인 6을 2로 나누고 나머지인 0을 push한다. 다시 그 몫인 3을 2로 나누고 나머지인 1을 push한다. 그 후 더이산 나눠지지 않는 몫인 1을 push한다. 2022.04.22 - [C++/자료구조] - 연결 리스트를 이용한 스택 구현 #include using namespace std; typedef int element; //int형 자료형에 element라 별칭 붙임. typedef struct Node //노드는 구조체 타입 { element Data; //스택 데이터를 정수 타입으로 가정 Node *Next..

중위표현 : 5+7처럼 연산자(Operator)가 피연산자(Operand)의 가운데에들어가는 표현이다. 후위표현 : 5 7 +처럼 연산자가 뒤로 가는 표현이다. 우리가 수식을 프로그램 할 때에는 중위표현을 사용하지만 이 표현은 나중에 컴파일러에 의해 후위표현으로 변환되어 실행된다. (2+5)*3-1 의 후위표현은 2 5 + 3 * 1 - 가 된다. 이 후위표현을 가지고 연산을 실행하면 다음과 같다. 언제라도 피 연산자가 들어오면 스택에 push한다. 연산자가 들어오면 스택에 쌓인 피연산자 두 개에 대해 해당 연산을 가하고 그 결과를 다시 스택에 푸시한다. 단, 그림처럼 먼저 팝 된 피연산자가 연산자의 오른쪽으로 가게 해서 연산을 가한다. 후위 연산의 연산과정을 코드로 나타내면 다음과 같다. #includ..

2022.04.22 - [C++/자료구조] - 스택(stack) - 2 화면에 STACK 이라는 단어를 입력한다고 가정해보자. 오류로 인해 STA 다음의 문자를 V로 입력했다면 그 즉시 백 스페이스 키()를 치고 다시 C를 입력하게 될 것이다. 만약, 어떤 사람이 KYOTWREA 순서로 입력하였다면 화면에 보이는 최종 단어는 KOREA가 된다. 새로운 문자가 입력될때마다 현재 문자열 끝에 추가하되 백 스페이스가 입력되면 현재 문자열의 마지막 문자를 삭제해야 한다. 이렇게 하면 위 예의 문제는 K, KY, K, KO, KOT, KOTW, KOT, KO, ... 의 순으로 변하게 된다. 따라서 프로그램은 현재 문자열 끝에 데이터를 삽입하는 기능과 함께, 마지막 문자를 삭제할 수 있는 기능이 필요하다. 아래는..

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..