Stack Expression Processing | Data Structure

괄호 검사여는 괄호는 push, 닫는 괄호는 맨 위와 짝이 맞을 때 pop한다.

실패하는 세 경우빈 스택에서 닫는 괄호, 종류가 어긋난 짝, 입력 끝에 남은 여는 괄호다.

후위식 평가연산자를 만나면 오른쪽 값, 왼쪽 값 순서로 두 번 pop해 계산한다.

괄호 검사는 짝을 찾지 못한 여는 괄호만 스택에 남긴다

입력과 읽은 기호 수를 바꾸면 현재 기호, 스택에 하는 일, 남은 여는 괄호, 판정이 바뀐다.

입력

스택 (바닥 → 맨 위)

위 줄은 입력 기호이며 파란 칸은 이미 읽은 기호, 초록 테두리 칸은 방금 읽은 기호, 빨간 칸은 실패를 일으킨 기호다. 아래 줄은 아직 짝을 찾지 못한 여는 괄호다.

식과 읽은 토큰 수를 바꾸면 값 스택, 방금 한 계산, 중간 결과가 바뀐다.

후위식

값 스택 (바닥 → 맨 위)

위 줄은 토큰이며 파란 칸은 읽은 토큰, 초록 테두리 칸은 방금 읽은 토큰이다. 아래 줄은 값 스택이고 초록 칸이 방금 넣은 값이다.