[DS] Evaluation of expression (수식의 평가)

# 수식의 평가

- 수식(expression): 연산자(operator)와 피연산자(operand)로 구성된 문장

- 연산자의 종류: 산술 연산자(arithmetic), 논리 연산자(logic), 대입 연산자(assignment) 등

- 피연산자의 종류: 변수(variable) 또는 상수(constant)

- 수식의 표기법

 

 

 

# 연산자 우선순위

- 우선순위 (precedence): 아래의 표에서 번호가 높을수록 우선순위가 높음

- 결합성(associativity) 규칙: 연산의 방향을 결정 (왼 → 오 / 오 →왼)

연산자 우선 순위

 

 

# 중위 표기법 vs 후위 표기법

 

 

 

# 후위 수식 계산 알고리즘

- 후위 수식의 평가: (5 7 * 9 + 3 4 / -)

 

- 수식 평가 스택

  > stack: 정수 배열로 선언된 수식 평가 스택

  > expr: 입력 문자 사이에 공백이 없는 단순 수식을 저장하고 있는 문자열

  > 연산자: (, ) ,= , -, *, /, %, '\0'

  > 피연산자: 0~9의 한자리 정수로 제한

// 수식 평가 스택
#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100

typedef enum{
    open_b, close_b, plus, minus, times, divide, mod, eos, operand
}priority;

int stack[STACK_SIZE];  // 수식 평가 스택
char expr[EXPR_SIZE];  // 수식 문자열
int pos =0;  // 문자열 현재 위치
char sym; // 읽어들인 문자
int sym_type;  // 읽어들인 문자의 종류
int top = -1

 

- 후위 수식(postfix)의 평가

  > eval_postfix: 수식 평가 함수로써 입력(문자)이 피연산자이면 정수로 변환한 후 스택에 넣고,

     입력이 연산자이면 피연산자 2개를 꺼내어 입력인 연산자로 연산을 한 후 결과를 스택에 다시 넣음

  > 입력은 문자로 들어오기 때문에 정수로 변환하여 스택에 넣어야 함 (입력문자 - '0')

void print_stack();
void push(int item);
int pop();
int eval_postfix();

void main(){
    //strcpy(expr, "57*9+34/-");
    strcpy(expr,"936+5-/7*64-*");
    eval_postfix();
}

void print_stack(){
    int i;
    for(i=0;i<=top;i++){
        printf("%d ",stack[i]);
    }
    printf("\n");
}
void push(int item){
    if(top>=STACK_SIZE - 1){
        printf("stack full");
        return;
    }
    stack[++top]=item;
    print_stack();
}

int pop(){
    if(top<0){
        printf("stack empty");
        return -999;
    }
    return stack[top--];
}

int eval_postfix(){
    int op1, op2;
    sym = read_item();
    while(sym_type!=eos){
        if(sym_type == operand) push(sym-'0');
        else{
            op2 = pop();
            op1 = pop();
            switch(sym_type){
                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); break;
            }
        }
        sym=read_item();
    }
    return pop();
}

 

- 심볼 입력

  > read_item: 수식에서 입력(문자)과 입력의 종류(0~8)를 함께 얻어옴

  > priority 열거형으로 선언되었기 때문에 내부적으로 0~8 사이의 정수 값을 가짐

  > 0~7은 연산자이고 8은 피연산자를 의미

char read_item();
char read_item(){
    sym = expr[pos++];
    
    switch(sym){
        case '(': sym_type = open_b; break;
        case ')': sym_type = close_b; break;
        case '+': sym_type = plus; break;
        case '-': sym_type = minus; break;
        case '*': sym_type = times; break;
        case '/': sym_type = divide; break;
        case '%': sym_type = mod; break;
        case '\0': sym_type = eos; break;
        default: sym_type = operand;
    }
    
    return sym;
}

 

- 후위 수식 평가 구현

[코드]

#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100

typedef enum{
    open_b, close_b, plus, minus, times, divide, mod, eos, operand
}priority;

int stack[STACK_SIZE];  // 수식 평가 스택
char expr[EXPR_SIZE];  // 수식 문자열
int pos =0;  // 문자열 현재 위치
char sym; // 읽어들인 문자
int sym_type;  // 읽어들인 문자의 종류
int top = -1;

char read_item();
void print_stack();
void push(int item);
int pop();
int eval_postfix();

void main(){
    //strcpy(expr, "57*9+34/-");
    strcpy(expr,"936+5-/7*64-*");
    eval_postfix();
}

char read_item(){
    sym = expr[pos++];

    switch(sym){
        case '(': sym_type = open_b; break;
        case ')': sym_type = close_b; break;
        case '+': sym_type = plus; break;
        case '-': sym_type = minus; break;
        case '*': sym_type = times; break;
        case '/': sym_type = divide; break;
        case '%': sym_type = mod; break;
        case '\0': sym_type = eos; break;
        default: sym_type = operand;
    }

    return sym;
}

void print_stack(){
    int i;
    for(i=0;i<=top;i++){
        printf("%d ",stack[i]);
    }
    printf("\n");
}
void push(int item){
    if(top>=STACK_SIZE - 1){
        printf("stack full");
        return;
    }
    stack[++top]=item;
    print_stack();
}

int pop(){
    if(top<0){
        printf("stack empty");
        return -999;
    }
    return stack[top--];
}

int eval_postfix(){
    int op1, op2;
    sym = read_item();
    while(sym_type!=eos){
        if(sym_type == operand) push(sym-'0');
        else{
            op2 = pop();
            op1 = pop();
            switch(sym_type){
                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); break;
            }
        }
        sym=read_item();
    }
    return pop();
}

 

[실행결과]

case 1: 5 7 * 9 + 3 4 / -

case 2: 9 3 6 + 5 - / 7 * 6 4 - *

 

 

 

# 중위 수식에서 후위 수식으로 변환

 

> 수동 방법은 여러번의 스캔이 필요함

> 한번에 읽어 계산하는 방법이 필요하게 됨

 

 

- 예제: 다음 중위 수식(infix)을 스택을 이용하여 후위 수식(postfix)으로 변환하시오

a + (b * c + d) * e

 

- 중위 수식을 후위 수식으로 변환

  > 연산자를 저장하기 위한 문자형 스택, push, pop 함수 필요

  > pos: 문자열에서 현재 입력을 읽기 위한 인덱스

  > 문자를 읽은 후 pos를 증가시켜 다음 입력의 위치를 가리키도록 함

  > isalnum 함수: 입력을 검사하여 숫자 또는 알파벳이면 피연산자로 간주하여 출력

 

[코드]

 

// 중위 수식에서 후위 수식 변환
#include<stdio.h>
#include<ctype.h>
#define STACK_SIZE 100

char token_stack[STACK_SIZE];
int token_top = -1;
void infix_to_postfix();
int precedence(char op);
void push_token(char sym);
char pop_token();

int main(){
    infix_to_postfix();
    return 0;
}

void infix_to_postfix(){
    char expr[50], sym, token;
    int pos=0;

    printf("Enter the expression ::");
    scanf("%s",expr) ; // 입력 받음

    while((token = expr[pos++])!='\0'){
        if(isalnum(token)) printf("%c ", token); // 알파벳 또는 숫자 = operand
        else if(token=='(') push_token(token);
        else if(token==')'){ // '('이 나올 때 까지 모든 연산자 출력력
           while((sym=pop_token())!='(') printf("%c ",sym);
        }
        else{
            while(precedence(token_stack[token_top])>=precedence(token)&&token_top!=-1){
                printf("%c ",pop_token());
            }
            push_token(token); // token > token_stack[token_top]
        }
    }
    while(token_top!=-1) printf("%c ",pop_token()); // 남아 있는 모든 원소 출력
}

int precedence(char op){ // 우선 순위를 반환해 줌
    if(op=='(') return 0; // 우선순위가 가장 낮음
    if(op=='+' || op=='-') return 1;
    if(op=='*' || op=='/' || op=='%') return 2;
}

void push_token(char sym){
    if(token_top<STACK_SIZE-1) token_stack[++token_top] = sym;
    else printf("token stack full\n");
}

char pop_token(){
    if(token_top>=0) return token_stack[token_top--];
    printf("token stack empty\n");
    return ' ';
}

 

[실행결과]

case 1

case 2