Cohe
5장 스택 응용 본문
728x90
후위표기법
- 후위표기법은 연산자를 피연산자의 뒤에 놓는 방법이다. 스택 응용의 예시이며 수식의 계산은 계산기에서나 컴퓨터 프로그래밍을 할 때 자주 나타난다.
- 우리가 평소에 쓰는 표기법은 중위 표기법이다.
- 곱하기. 나누기 연산자가 +.-연산자보다 먼저 계산해야하며 곱하기 나누기 연산자와 +-가 동시에 있으면 왼쪽에 있는 식부터 계산해야하는 것을 알고 있기 때문이다.
수식의 계산
사람
- 연산자의 우선 순위를 정한다. 우선순위가 같으면 왼쪽 부터인지 오른쪽부터인지 정한다.
- 복잡하면 괄호를 사용하여 계산한다.
컴퓨터
- 사람이 하는 방법 대로 계산할 수도 있지만 중간과정을 줄이고 한번에 왼쪽에서 오른쪽으로 계산할 수 있는 효율적인 방법을 개발
- 수식의 후위식으로 바꾼다.
- 후위식을 계산한다.
C언어의 우선순위 표
수식 계산
- 수식을 후위 표기법으로 바꾼다.
- 중위표기법 : 연산자를 피연산자 가운데 놓는 방법이다.
- 후위표기법 : 연산자를 피연산자 뒤에 놓고 표기하는 방법
- 사람은 연산자 사이의 구분이 어려워 중위 표기법이 간편하다고 생각.
- 예시
- 3*5+4
- 후위표기법: 35*4+
- 3*(5+4)
- 후위 표기법 : 354+* → 괄호가 필요가 없어진다
- 3*5+4
- 후위식을 계산한다.
- 후위식은 중위식과 계산방법이 다르다.
- 중위식처럼 식의 왼쪽, 오른쪽 우선순위에 따라 옮겨 다니지 않고 왼쪽부터 연산자가 나오는 순서대로 계산
- ex)
- 35*4+
- 1단계 : 35*을 계산하여 저장
- 2단계 15 4+를 계산하여 저장
- 19
- 괄호가 있는 것의 경우 괄호가 끝나고 난 뒤에 계산이 가능하다. 컴퓨터의 입장에서 귀찮음.
- 중위식과 후위식의 알고리즘을 비교하면 후위식이 훨씬 편리하다. 알고리즘이 간단하고 효율적이기 때문.
- operator (연산자), 계산한다./ operand(피연산자) : 갖고 있는다.
중위표기를 후위표기로 바꾸기
- 중위식에 괄호를 친 다음 연산자를 괄호 뒤로 옮긴 후 괄호를 지운다.
스택을 이용한 후위표기법 변환
- 피연산자는 출력한다
- 연산자는 앞 연산자를 살펴서 출력하거나 대기한다
- 스택에 넣는다. 대기딘 자료들은 나중에 대기 된 연산자가 먼저 나온다.
- 연산자의 대기여부는 연산자간의 우선순위에 따른다.
입력단계 별 스택 출력 결과
- 연산자의 경우 스택에 쌓아두며 연산자 우선순위가 높은 순으로 쌓아둔다.
- 피연산자는 출력해야한다.
- 중위표현식을 후위표현식으로 바꾸는 연산을 수행하는 과정을 표로 표기한 것이다.
- 후에 들어온 연산자의 우선순위가 높은 경우 원래 있던 연산자를 출력하고 후에 들어온 연산자를 스택에 저장한다.
괄호가 있는 경우
- 우선순위가 가장 큰 것.
- 그냥 연산자 취급을 한다. 스택에 들어가서 표시하는 역할을 한다.
- 왼쪽 괄호 전에는 계산을 할 수 없으니 스택에 삽입되어 기다린다.
- )가 나온 경우 스택에 있는 것을 꺼내준다. 왼쪽 괄호는 버린다.
괄호가 있는 경우
- 우선순위가 가장 큰 것.
- 그냥 연산자 취급을 한다. 스택에 들어가서 표시하는 역할을 한다.
- 왼쪽 괄호 전에는 계산을 할 수 없으니 스택에 삽입되어 기다린다.
- )가 나온 경우 스택에 있는 것을 꺼내준다. 왼쪽 괄호는 버린다.
code
/* 수식을 읽어서 연산자(operator), 피연산자(operand) 구분해보기 */
/* (1) 다른 수식을 입력하여 테스트 해본다. */
/* (2) 피연산자만 출력해본다. 연산자는 저장했다가 수식이 끝나면 출력한다. */
/* (3) 피연산자만 출력해본다. 스택을 만들어
/* 연산자는 스택에 넣고 수식이 끝나면 모두 출력한다. */
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <string.h>
int get_token(char *token, int *n) {
char symbol;
symbol = token[*n];
*n = *n + 1;
switch (symbol) {
case '(': return 0;
case ')': return 1;
case '+': return 2;
case '-': return 3;
case '/': return 4;
case '*': return 5;
case '%': return 6;
case ' ': return 7;
default: return 8;
}
}
int main()
{
char myexpr[10];
int token=0; int n = 0;
strcpy(myexpr, "3+2*5-4 "); // 수식 - 입력의 마지막에 공백(eos)을 둔다.
for ( ; token != 7; )
{
token = get_token(myexpr, &n);
if (token == 8) printf("%s ", "operand");
else printf("%s ", "operator");
// else printf("%d ", token);
}
printf("\\n");
}
- main
- 수식 중 eos 표시를 위해 공백을 만들었다.
int main() { char myexpr[10]; int token=0; int n = 0; strcpy(myexpr, "3+2*5-4 "); // 수식 - 입력의 마지막에 공백(eos)을 둔다. for ( ; token != 7; ) { token = get_token(myexpr, &n); if (token == 8) printf("%s ", "operand"); else printf("%s ", "operator"); // else printf("%d ", token); } printf("\\n"); } - get_token
int get_token(char *token, int *n) {
char symbol;
symbol = token[*n];
*n = *n + 1;
switch (symbol) {
case '(': return 0;
case ')': return 1;
case '+': return 2;
case '-': return 3;
case '/': return 4;
case '*': return 5;
case '%': return 6;
case ' ': return 7;
default: return 8;
}
}알고리즘
중위식을 후위식으로 바꾸기
- 알고리즘
#중위식을 후위표기로 바꾸는 프로그램
{
while (입력 token이 있는 동안 반복){
입력에서 토큰을 가져온다
if (token==operand) 토큰을 출력
elif (token==operator){
operator(token)의 우선순위가 높거나 같으면 스택의 operatorㅇ,ㄹ pop()하는 작업을 반복한다.
operatordms push() 한다.}
elif(token==왼쪽괄호) { 스택에 push() 한다. }
else(token==오른쪽 괄호){
스택에 왼쪽 괄호를 만날 때 까지 pop()하여 출력한다}
스택에 있는 operator을 모두 pop()한다.}2. 실제 코드
/* 프로그램 5-1 중위식-후위식 변환 : infixtopostfix.c */
#define _CRT_SECURE_NO_WARNINGS
/*p2*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* max size of expression */
/*열거형 타입 precedence 선언*/
typedef enum {lparen, rparen, plus, minus, times, divide,
mod, eos, operand } precedence;
char expr[MAX_EXPR_SIZE]; /* input string */
int top = -1;
precedence stack[MAX_STACK_SIZE];
/* isp and icp arrays ? index is value of precedence lparen, rparen,
plus, minus, times, divide, mode, eos */
void push(precedence item)
{
if(top >= MAX_STACK_SIZE - 1) {
printf("stack_full()\n");
return;
}
stack[++top] = item;
}
precedence pop() {
if(top == -1)
{
printf("stack_empty()\n");
}
return stack[(top)--];
}
int isempty()
{ if( top == -1 ) return(1); else return(0); }
int isfull()
{ if ( top >= MAX_STACK_SIZE -1 ) return(1); else return(0); }
/*오른 쪽 괄호는 우선순위를 높게 함, 비교를 할 이유가 없음
왼 괄호에 대한 것은 중요하다. stack에 들어갈 때는 우선순위가 낮도록 하고
나올 때는 굉장히 높게 함.
스택에 저장되어야 하기 때문이며 우선 순위가 낮을 수록 쌓이고 높을수록 저장될 수 있다.
ex) 곱셈이 들어올 때 덧셈보다 우선순위가 높으면 덧셈보다 상위 스택에 저장됨
곱셈 이후에 덧셈이 들어오면 우선순위가 낮기 때문에 곱셈 스택을 빼내고 덧셈을 넣음
*/
static int isp[] = {0,19,12,12,13,13,13,0};
static int icp[] = {20,19,12,12,13,13,13,0}; // lparen 연산자 우선순위 조정
/*입력에서 토큰을 받아들이는 프로그램*/
precedence get_token(char *symbol, int *n) {
*symbol = expr[(*n)++];
switch(*symbol) {
case '(': return lparen;
case ')': return rparen;
case '+': return plus;
case '-': return minus;
case '/': return divide;
case '*': return times;
case '%': return mod;
case ' ': return eos;
default: return operand;
}
}
precedence print_token(precedence t) {
switch(t) {
case lparen : printf("( " ); break;
case rparen : printf(") " ); break;
case plus : printf("+ " ); break;
case minus : printf("- " ); break;
case divide : printf("/ " ); break;
case times : printf("* " ); break;
case mod : printf("% " ); break;
case eos : printf("eos " ); break;
default: printf("\n "); return(0);
}
}
/*중위 표기를 후위표기로 바꾸는 프로그램*/
void postfix(void) {
char symbol;
precedence token;
int n = 0;
top = 0;
stack[0] = eos; // 스택의 바닥에 공백(eos)를 넣는다.
for(token = get_token(&symbol, &n); token != eos; token = get_token(&symbol, &n))
{
if(token == operand) printf("%c ", symbol);
else if(token == rparen) { // 오른쪽 괄호 만나면 스택에서 모두 pop..
while(stack[top] != lparen)
print_token(pop());
pop();
}
else { // 연산자들의 우선 순위 비교..
while(isp[stack[top]] >= icp[token])
print_token(pop());
push(token);
}
}
while((token = pop()) != eos)
print_token(token);
printf(" \n");
}
int main()
{
strcpy(expr, "3+2*5-4 "); // 입력의 마지막에 공백(eos)을 둔다.
postfix();
}- 연산자 입력시 스택 처리
- if 우선순위의 우열을 어떻게 구별해야할까?
- 알고리즘~
스택을 이용한 후위표기법의 계산
후위표기 식의 계산
- 괄호가 필요없다
- 연산자 우선순위가 필요없다
프로그램 복잡도
- 시간 : O(r)
- 기억 공간 S(n)=n
방금 한 것의 알고리즘
- 피연산자면 스택에 집어넣는다
- 연산자면 pop을 두번 해서 계산 후 push한다
/* 프로그램 5-2 후위식 계산 : postfixeval.c */
#define _CRT_SECURE_NO_WARNINGS // Visual Studio 2013 용
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* max size of expression */
typedef enum {lparen, rparen, plus, minus, times, divide,
mod, eos, operand } precedence;
char expr[MAX_EXPR_SIZE]; /* input string */
int top = -1;
int stack[MAX_STACK_SIZE];
/* isp and icp arrays ? index is value of precedence lparen, rparen,
plus, minus, times, divide, mode, eos */
/*p1*/
void push(int item)
{
if(top >= MAX_STACK_SIZE - 1) {
printf("stack_full()\\n");
return;
}
stack[++top] = item;
}
int pop() {
if(top == -1)
{
printf("stack_empty()\\n"); //exit();
}
return stack[(top)--];
}
int isempty()
{ if( top == -1 ) return(1); else return(0); }
int isfull()
{ if ( top >= MAX_STACK_SIZE -1 ) return(1); else return(0); }
static int isp[] = {0,19,12,12,13,13,13,0};
static int icp[] = {20,19,12,12,13,13,13,0};
precedence get_token(char *symbol, int *n) {
*symbol = expr[(*n)++];
switch(*symbol) {
case '(': return lparen;
case ')': return rparen;
case '+': return plus;
case '-': return minus;
case '/': return divide;
case '*': return times;
case '%': return mod;
case ' ': return eos;
default: return operand;
}
}
precedence print_token(precedence t) {
switch(t) {
case lparen : printf("(" ); break;
case rparen : printf(")" ); break;
case plus : printf("+" ); break;
case minus : printf("-" ); break;
case divide : printf("/" ); break;
case times : printf("*" ); break;
case mod : printf("%" ); break;
case eos : printf("eos" ); break;
default: printf("\\n");
}
}
int eval(void)
{
precedence token;
char symbol;
int op1, op2;
int n = 0;
top = -1;
token = get_token(&symbol, &n);
while (token != eos) {
if(token == operand)
push(symbol-'0');
else {
op2 = pop();
op1 = pop();
switch(token) {
case plus: push(op1 + op2);break;
case minus: push(op1 - op2);break;
case times: push(op1 * op2);break;
case divide: push(op1 / op2);break;
case mod: push(op1 % op2);
}
}
token = get_token(&symbol, &n);
}
return pop();
}
int main()
{
strcpy(expr, "32+ ");
printf("* Begin evaluation ... %s\\n", expr);
printf("* The result is => %d\\n", eval());
}
연습문제
- 스택에서 push(), pop() 일어날 때마다 스택의 원소를 모두 출력해보도록 프로그램을 수정하여 보아라, print_stack() 함수를 만들어 push()pop() 후에 호출하여본다.
/* 프로그램 5-1 중위식-후위식 변환 : infixtopostfix.c */
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* max size of expression */
typedef enum {
lparen, rparen, plus, minus, times, divide,
mod, eos, operand
} precedence;
char expr[MAX_EXPR_SIZE]; /* input string */
int top = -1;
precedence stack[MAX_STACK_SIZE];
/* isp and icp arrays ? index is value of precedence lparen, rparen,
plus, minus, times, divide, mode, eos */
void push(precedence item)
{
if (top >= MAX_STACK_SIZE - 1) {
printf("stack_full()\n");
return;
}
stack[++top] = item;
}
precedence pop() {
if (top == -1)
{
printf("stack_empty()\n");
}
return stack[(top)--];
}
int isempty()
{
if (top == -1) return(1); else return(0);
}
int isfull()
{
if (top >= MAX_STACK_SIZE - 1) return(1); else return(0);
}
static int isp[] = { 0,19,12,12,13,13,13,0 };
static int icp[] = { 20,19,12,12,13,13,13,0 }; // lparen 연산자 우선순위 조정
precedence get_token(char* symbol, int* n) {
*symbol = expr[(*n)++];
switch (*symbol) {
case '(': return lparen;
case ')': return rparen;
case '+': return plus;
case '-': return minus;
case '/': return divide;
case '*': return times;
case '%': return mod;
case ' ': return eos;
default: return operand;
}
}
precedence print_token(precedence t) {
switch (t) {
case lparen: printf("( "); break;
case rparen: printf(") "); break;
case plus: printf("+ "); break;
case minus: printf("- "); break;
case divide: printf("/ "); break;
case times: printf("* "); break;
case mod: printf("% "); break;
case eos: printf("eos "); break;
default: printf("\n "); return(0);
}
}
void print_Stack(int top) {
if (stack != 0) {
for (int i = top; stack[i]!=eos; i--) {
printf("In the stack : %d", stack[i]);
}
printf("\n");
}
}
void postfix(void) {
char symbol;
precedence token;
int n = 0;
top = 0;
stack[0] = eos; // 스택의 바닥에 공백(eos)를 넣는다.
for (token = get_token(&symbol, &n); token != eos; token = get_token(&symbol, &n))
{
if (token == operand) {
printf("%c ", symbol); //stack 원소가 뭐가 있는지 알려주는 듯
print_Stack(top);
}
else if (token == rparen) { // 오른쪽 괄호 만나면 스택에서 모두 pop..
print_Stack(top);
while (stack[top] != lparen)
print_token(pop());
pop();
}
else { // 연산자들의 우선 순위 비교..
while (isp[stack[top]] >= icp[token])
print_token(pop());
push(token);
}
}
while ((token = pop()) != eos) {
print_token(token);
}
printf(" \n");
}
int main()
{
strcpy(expr, "3+2*5-4 "); // 입력의 마지막에 공백(eos)을 둔다.
postfix();
}- 스택에서 push(), pop()일어날 때마다 스택의 원소를 모두 출력해보도록 프로그램을 수정하여 보기
- print_stack()함수를 만들어서 push, pop 후에 호출해본다
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* max size of expression */
typedef enum {
lparen, rparen, plus, minus, times, divide,
mod, eos, operand
} precedence;
char expr[MAX_EXPR_SIZE]; /* input string */
int top = -1;
int stack[MAX_STACK_SIZE];
/* isp and icp arrays ? index is value of precedence lparen, rparen,
plus, minus, times, divide, mode, eos */
void push(int item)
{
if (top >= MAX_STACK_SIZE - 1) {
printf("stack_full()\\n");
return;
}
stack[++top] = item;
print_stack();
}
int pop() {
if (top == -1)
{
printf("stack_empty()\\n"); //exit();
}
int oldtop = top;
top--;
print_stack();
return stack[oldtop];
}
int isempty()
{
if (top == -1) return(1); else return(0);
}
int isfull()
{
if (top >= MAX_STACK_SIZE - 1) return(1); else return(0);
}
static int isp[] = { 0,19,12,12,13,13,13,0 };
static int icp[] = { 20,19,12,12,13,13,13,0 };
precedence get_token(char* symbol, int* n) {
*symbol = expr[(*n)++];
switch (*symbol) {
case '(': return lparen;
case ')': return rparen;
case '+': return plus;
case '-': return minus;
case '/': return divide;
case '*': return times;
case '%': return mod;
case ' ': return eos;
default: return operand;
}
}
precedence print_token(precedence t) {
switch (t) {
case lparen: printf("("); break;
case rparen: printf(")"); break;
case plus: printf("+"); break;
case minus: printf("-"); break;
case divide: printf("/"); break;
case times: printf("*"); break;
case mod: printf("%"); break;
case eos: printf("eos"); break;
default: printf("\\n");
}
}
int eval(void)
{
precedence token;
char symbol;
int op1, op2;
int n = 0;
top = -1;
token = get_token(&symbol, &n);
while (token != eos) {
if (token == operand)
push(symbol - '0');
else {
op2 = pop();
op1 = pop();
switch (token) {
case plus: push(op1 + op2); break;
case minus: push(op1 - op2); break;
case times: push(op1 * op2); break;
case divide: push(op1 / op2); break;
case mod: push(op1 % op2);
}
}
token = get_token(&symbol, &n);
}
return pop();
}
**int print_stack() {
printf("Stack: [");
for (int i = 0; i <= top; i++) {
print_token(stack[i]);
// printf(" %c", stack[i]);
}
printf(" ]\\n");
}**
int main()
{
strcpy(expr, "32+ ");
printf("* Begin evaluation ... %s\\n", expr);
print_stack();
printf("* The result is => %d\\n", eval());
}