[6] 스택 ⑦ 스택의 응용 : 후위수식 변환

728x90

[ 문제 2 ] 후위로 변환된 수식을 입력받아 스택을 사용하여 계산한 후 결과 값을 출력하는 프로 그램을 작성하시오

스택은 배열이나 연결리스트로 구현함
수식의 피연산자는 0에서 9 사이의 정수이고, 각 수식의 최대길이는 100으로 함
수식의 연산자는 곱하기, 나누기, 더하기, 빼기로 구성되며, 정수 연산 수행
- 즉, 나누기의 경우, 몫 계산 ※ 예제 : 82/3-

입출력에 대한 설명 (아래 입출력 예시 참조)

1) 첫 번째 라인 : 수식의 개수
2) 두 번째 라인 :

- 하나의 줄에 후위수식이 공백 없이 입력됨

정답 코드 파일

문제 풀이 [1] : 전역 변수 사용

헤더 선언

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top, sign;

• top은 스택의 가장 위에 있는 요소의 인덱스를 저장하는 전역 변수이다.

push 함수 / pop 함수

void push(int *arr, int ch) {
	top++;
	arr[top] = ch;
}

int pop(int *arr) {
	int data;
	data = arr[top];
	top--;
	return data;
}

push 함수는 스택에 요소를 추가하는 함수이다.

arr은 스택을 나타내는 배열을 가리키는 포인터이며, ch는 스택에 추가할 요소이다.

top 변수를 증가시키고, 그 인덱스에 해당하는 배열 요소에 ch를 할당하여 스택에 요소를 추가한다.

pop 함수는 스택에서 요소를 제거하고 반환하는 함수이다.

arr은 스택을 나타내는 배열을 가리키는 포인터입니다.

가장 위에 있는 요소를 data 변수에 저장한 후, top을 감소시켜 다음으로 접근할 요소의 인덱스를 업데이트한다.

마지막으로 data를 반환한다.

order 함수 : 연산자의 우선 순위 반환

int order(char op) {
	switch (op) {
    	case '+': return 1;
    	case '-': return 2;
    	case '*': return 3;
    	case '/': return 4;
    	default: return 0;
	}
}

주어진 연산자가 어떤 우선순위를 갖는지 결정하는 함수를 구현한다.

주어진 연산자에 따라 해당 연산자의 우선순위를 반환한다. '+' 연산자의 경우 1을 반환하고, '-' 연산자의 경우 2를 반환하며, '*' 연산자의 경우 3을 반환하고, '/' 연산자의 경우 4를 반환한다. 주어진 연산자가 이에 해당하지 않는 경우, 즉 다른 연산자이거나 오타인 경우에는 0을 반환한다.

이 함수를 사용하면 주어진 연산자의 우선순위를 알 수 있어서, 연산자 우선순위에 따라 수식을 계산하거나 연산자를 적절한 순서로 처리할 수 있다.

evaluate 함수

void evaluate(char *arr){
	int sta[101] = { 0 };
	int num1, num2;
	for (int i = 0; i < strlen(arr); i++) {
		if (order(arr[i]) == 0)
			push(sta, arr[i] - '0');
			
		else if (order(arr[i]) == 1) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num1 + num2);
		}
		else if (order(arr[i]) == 2) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num2 - num1);
		}
		else if (order(arr[i]) == 3) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num2 * num1);
		}
		else if (order(arr[i]) == 4) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num2 / num1);
		}
	}
	printf("%d\n", pop(sta));
}

이 함수는 문자열로 표현된 수식을 평가하여 결과를 출력하는 기능을 수행한다.

1. 문자열에 있는 각 문자를 하나씩 확인한다.

2. 만약 현재 문자가 연산자가 아니라면, 즉 숫자라면 해당 숫자를 스택에 집어넣는다.

3. 숫자를 스택에 넣을 때에는 해당 문자를 정수형 숫자로 변환하여 저장한다.

4. 만약 현재 문자가 연산자라면, 스택에서 두 개의 숫자를 꺼내어 해당 연산을 수행한다.

- 덧셈 연산인 경우: 두 숫자를 더한 결과를 스택에 넣는다.

- 뺄셈 연산인 경우: 두 숫자를 뺀 결과를 스택에 넣는다. 이때, 먼저 꺼낸 숫자에서 나중에 꺼낸 숫자를 뺀다.

- 곱셈 연산인 경우: 두 숫자를 곱한 결과를 스택에 넣는다.

- 나눗셈 연산인 경우: 두 숫자를 나눈 결과를 스택에 넣는다. 이때, 먼저 꺼낸 숫자를 나머지 숫자로 나눈다.

5. 모든 문자를 처리한 후에는 스택에 최종 결과가 남게 된다. 이 결과를 출력한다.

main 함수

int main() {
	char str[101] = { NULL };
	int N;
	scanf("%d", &N);
	getchar();
	for (int i = 0; i < N; i++) {
		top = -1;
		sign = 0;
		gets(str);
		evaluate(str);
	}
}

사용자로부터 입력을 받아 문자열로 표현된 수식을 평가하고, 그 결과를 출력하는 프로그램을 구현한다.

main 함수는 프로그램의 시작점이다.
먼저, 변수 str을 선언하고 크기가 101인 문자열로 초기화한다.
정수형 변수 N을 선언하고, 사용자로부터 입력을 받아 할당한다. 이 변수는 수식의 개수를 나타낸다.
사용자로부터 입력받은 후에는 개행 문자(\n)를 처리하기 위해 getchar() 함수를 호출한다.
반복문을 통해 N번의 반복을 수행한다.
매 반복마다 스택의 상태를 초기화하기 위해 top과 sign 변수를 -1과 0으로 초기화한다.
gets() 함수를 사용하여 사용자로부터 문자열을 입력받고, 이를 str 배열에 저장한다.
입력받은 수식을 평가하기 위해 evaluate() 함수를 호출한다.

이렇게 하면 사용자가 입력한 각 수식에 대해 평가된 결과를 출력할 수 있다.

문제 풀이 [2] : 스택 배열 이용

헤더 및 구조체 선언

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef int element;
#define MAX_SIZE 100 //배열 스택 사이즈

typedef struct {
    char data[MAX_SIZE]; // 스택의 데이터를 저장할 배열
    int top; // 스택의 최상위 원소의 인덱스를 나타내는 변수
    int max;
} Stack;

이 코드는 C 언어를 사용하여 스택(Stack)을 구현한다.

stdio.h, string.h, stdlib.h 헤더 파일을 포함한다.
typedef int element;는 스택에 저장되는 데이터의 타입을 int로 정의한다.
#define MAX_SIZE 100은 스택이 저장할 수 있는 최대 요소 수를 나타내는 상수다.
Stack 구조체는 스택을 구현하는데 사용된다. 이 구조체는 다음과 같은 멤버를 갖는다:
- data: 스택의 데이터를 저장하는 배열이다. 이 배열은 문자열로 정의된다.
- top: 스택의 최상위 원소의 인덱스를 나타내는 변수다.
- max: 스택의 최대 크기를 나타내는 변수다.

이러한 구조체를 사용하여 스택을 생성하고 조작할 수 있다. 스택은 데이터를 저장하고 추출하는 기능을 제공한다.

push 함수 / pop 함수

void push(Stack *stack, element e){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    stack->top ++; //스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    stack->data[stack->top] = e;
}

element pop(Stack *stack){
    // if(isEmpty(stack)) {printf("Stack Empty\n");return -1;}
    element del = stack->data[stack->top];
    stack->top --;
    return del-'0';
}

이 함수는 스택에 데이터를 추가(push)하고 제거(pop)하는 기능을 수행한다.

void push(Stack *stack, element e): 이 함수는 스택에 데이터를 추가한다.
- stack: 스택을 가리키는 포인터이다.
- e: 스택에 추가할 데이터이다.
- 함수 내부에서는 스택의 최상위 위치를 나타내는 top 변수를 증가시킨 후, 해당 위치에 데이터를 저장한다. 스택의 최상위 위치는 0부터 MAX_SIZE - 1까지이다.
element pop(Stack *stack): 이 함수는 스택에서 데이터를 제거하고 반환한다.
- stack: 스택을 가리키는 포인터이다.
- 함수 내부에서는 스택의 최상위 위치에 있는 데이터를 삭제한 후, 그 값을 반환한다. 그리고 최상위 위치를 하나 감소시킨다.
- 반환된 값은 문자 형태로 되어 있으므로, - '0'을 통해 정수 형태로 변환하여 반환한다.

주석 처리된 부분은 스택이 가득 차거나 비어 있는지 확인하는 함수를 호출하는 부분이다. 이 함수들은 주석처리되어 있으므로, 현재는 해당 기능이 사용되지 않는다.

order 함수 : 연산자의 우선 순위 반환

int order(char op) {
	switch (op) {
    	case '+': return 1;
    	case '-': return 2;
    	case '*': return 3;
    	case '/': return 4;
    	default: return 0;
	}
}

주어진 연산자가 어떤 우선순위를 갖는지 결정하는 함수를 구현한다.

이 함수를 사용하면 주어진 연산자의 우선순위를 알 수 있어서, 연산자 우선순위에 따라 수식을 계산하거나 연산자를 적절한 순서로 처리할 수 있다.

calaulate 함수

void calculate(char *arr){
    int num1,num2;
    int len = (int)strlen(arr);

    Stack rst;
    init(&rst);

    for(int i=0;i<len;i++){
        char c = arr[i];
        if( '0' <= c && c <= '9'){
            // printf("Number is [%d]\n",c-'0');
            push(&rst,c);
        }
        else{
            num2 = pop(&rst);
            num1 = pop(&rst);

            switch (order(c)){
                case 1:
                    // printf("[%d] + [%d] = %d\n",num1,num2,num1+num2);
                    push(&rst,(num1 + num2)+'0');break;
                case 2:
                    // printf("[%d] - [%d] = %d\n",num1,num2,num1-num2);
                    push(&rst,(num1 - num2)+'0');break;
                
                case 3:
                    // printf("[%d] * [%d] = %d\n",num1,num2,num1*num2);
                    push(&rst,(num1 * num2)+'0');break;

                default:
                    // printf("[%d] / [%d] = %d\n",num1,num2,num1/num2);
                    push(&rst,(num1 / num2)+'0');break;
            }
        }

    }
    printf("%d\n",pop(&rst));
}

이 함수는 주어진 문자열로 표현된 수식을 계산하고 결과를 출력하는 로직을 구현한다.

먼저, 입력된 문자열의 길이를 계산하여 저장한다.
결과를 저장할 스택을 초기화한다.
문자열을 하나씩 순회하면서 각 문자가 숫자인지 확인한다.
만약 숫자라면, 해당 숫자를 스택에 추가한다(push).
숫자가 아니라면, 스택에서 두 개의 숫자를 꺼내어(pop) 해당 연산을 수행하고 그 결과를 다시 스택에 추가한다(push).
마지막으로 스택에 남은 결과를 출력한다.

이 방식으로 함수는 주어진 수식을 순차적으로 평가하여 최종 결과를 스택을 통해 구한다.

main 함수

int main() {
    Stack stack;
    int n; scanf("%d",&n); getchar();
    for(int i=0;i<n;i++){
        init(&stack);
        scanf("%s",stack.data);
        calculate(stack.data);
    }

}

이 코드는 주어진 수식들을 입력받아 계산하는 메인 함수를 구현한다.

int main(): 프로그램의 진입점을 정의한다.
- Stack stack;: 스택을 선언한다.
- int n; scanf("%d",&n); getchar();: 사용자로부터 입력받은 수식의 개수를 저장할 변수 n을 선언하고, 입력을 받는다.
- for(int i=0;i<n;i++): 입력받은 수식의 개수만큼 반복한다.
  - init(&stack);: 반복문이 시작될 때마다 스택을 초기화한다.
  - scanf("%s",stack.data);: 문자열 형태로 수식을 입력받아 스택의 data 배열에 저장한다.
  - calculate(stack.data);: 입력받은 수식을 계산하여 결과를 출력한다.

이 코드는 사용자로부터 여러 개의 수식을 입력받아 각각을 평가하여 결과를 출력하는 기능을 제공한다.

정답 코드 [1]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top, sign;

void push(int *arr, int ch) {
	top++;
	arr[top] = ch;
}

int pop(int *arr) {
	int data;
	data = arr[top];
	top--;
	return data;
}

int order(char op) {
	switch (op) {
    	case '+': return 1;
    	case '-': return 2;
    	case '*': return 3;
    	case '/': return 4;
    	default: return 0;
	}
}

void evaluate(char *arr){
	int sta[101] = { 0 };
	int num1, num2;
	for (int i = 0; i < strlen(arr); i++) {
		if (order(arr[i]) == 0)
			push(sta, arr[i] - '0');
			
		else if (order(arr[i]) == 1) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num1 + num2);
		}
		else if (order(arr[i]) == 2) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num2 - num1);
		}
		else if (order(arr[i]) == 3) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num2 * num1);
		}
		else if (order(arr[i]) == 4) {
			num1 = pop(sta);
			num2 = pop(sta);
			push(sta, num2 / num1);
		}
	}
	printf("%d\n", pop(sta));
}
int main() {
	char str[101] = { NULL };
	int N;
	scanf("%d", &N);
	getchar();
	for (int i = 0; i < N; i++) {
		top = -1;
		sign = 0;
		gets(str);
		evaluate(str);
	}
}

정답 코드[2]

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef int element;
#define MAX_SIZE 100 //배열 스택 사이즈

typedef struct {
    char data[MAX_SIZE]; // 스택의 데이터를 저장할 배열
    int top; // 스택의 최상위 원소의 인덱스를 나타내는 변수
    int max;
} Stack;

void init(Stack *stack){stack->top = -1; }

int isEmpty(Stack *stack){return (stack->top == -1);}

int isFull(Stack *stack){return (stack->top ==( MAX_SIZE -1 ));}

void push(Stack *stack, element e){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    stack->top ++; //스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    stack->data[stack->top] = e;
}

element pop(Stack *stack){
    // if(isEmpty(stack)) {printf("Stack Empty\n");return -1;}
    element del = stack->data[stack->top];
    stack->top --;
    return del-'0';
}


int size(Stack *stack){ return stack->top + 1 ;}

element peek(Stack *stack){ //top과 기능 동일
    // if(isEmpty(stack)) printf("Stack Empty\n");
    return stack->data[stack->top];
}

void duplicate(Stack *stack){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    element dup = pop(stack);
    push(stack,dup); push(stack,dup);
}


void upRotate(Stack *stack, int n){
    // if(n > stack->top){printf("Stack FULL\n"); return ;}
    element e = stack->data[stack->top];
    for(int i=0;i<n;i++){
        stack->data[stack->top - i] = stack->data[stack->top - i - 1];
        // stack->data[stack->top - n + 1 + i] = stack->data[stack->top - n + 1 + i]
    }stack->data[stack->top - n + 1] = e;
}


void downRotate(Stack *stack, int n){
    // if(n > stack->top){printf("Stack FULL\n"); return ;}
    element e = stack->data[stack->top - n + 1];
    for(int i = stack->top - n + 1 ; i<= stack->top ; i++){
        stack->data[i] = stack->data[i+1];
    }stack->data[stack->top] = e;
}

int order(char op) {
	switch (op) {
    	case '+': return 1;
    	case '-': return 2;
    	case '*': return 3;
    	case '/': return 4;
    	default: return 0;
	}
}

void print(Stack *stack){
    // printf("[TOP] ");
    for(int i=stack->top ; i>=0 ; i--){
        printf("%c",stack->data[i]);
        // printf("[%c] ",stack->data[i]);
    }
    // printf("[BOTTOM]");
    printf("\n");
}

void calculate(char *arr){
    int num1,num2;
    int len = (int)strlen(arr);

    Stack rst;
    init(&rst);

    for(int i=0;i<len;i++){
        char c = arr[i];
        if( '0' <= c && c <= '9'){
            // printf("Number is [%d]\n",c-'0');
            push(&rst,c);
        }
        else{
            num2 = pop(&rst);
            num1 = pop(&rst);

            switch (order(c)){
                case 1:
                    // printf("[%d] + [%d] = %d\n",num1,num2,num1+num2);
                    push(&rst,(num1 + num2)+'0');break;
                case 2:
                    // printf("[%d] - [%d] = %d\n",num1,num2,num1-num2);
                    push(&rst,(num1 - num2)+'0');break;
                
                case 3:
                    // printf("[%d] * [%d] = %d\n",num1,num2,num1*num2);
                    push(&rst,(num1 * num2)+'0');break;

                default:
                    // printf("[%d] / [%d] = %d\n",num1,num2,num1/num2);
                    push(&rst,(num1 / num2)+'0');break;
            }
        }

    }
    printf("%d\n",pop(&rst));
}


int main() {
    Stack stack;
    int n; scanf("%d",&n); getchar();
    for(int i=0;i<n;i++){
        init(&stack);
        scanf("%s",stack.data);
        calculate(stack.data);
    }

    // init(&stack);
    // scanf("%s",stack.data);
    // printf(">>> %s\n",stack.data);
    // calculate(stack.data);
}

728x90

저작자표시

'Datastructure > [6] 스택' 카테고리의 다른 글

[6] 스택 ⑥ 스택의 응용 : 중위수식 변환 (0)	2024.05.17
[6] 스택 ⑤ 스택의 응용 : 괄호 (0)	2024.05.15
[6] 스택 ④ 스택의 응용 : 스택 ADT (0)	2024.05.13
[6] 스택 ③ 연결리스트를 이용한 스택 알고리즘(ADT) (0)	2024.05.13
[6] 스택 ② 배열을 이용한 스택 알고리즘(ADT) (0)	2024.05.12

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

우당탕탕 코딩 제작소

[6] 스택 ⑦ 스택의 응용 : 후위수식 변환

[ 문제 2 ] 후위로 변환된 수식을 입력받아 스택을 사용하여 계산한 후 결과 값을 출력하는 프로 그램을 작성하시오

정답 코드 파일

문제 풀이 [1] : 전역 변수 사용

헤더 선언

push 함수 / pop 함수

order 함수 : 연산자의 우선 순위 반환

evaluate 함수

main 함수

헤더 및 구조체 선언

push 함수 / pop 함수

order 함수 : 연산자의 우선 순위 반환

calaulate 함수

main 함수

정답 코드[2]

'Datastructure > [6] 스택' 카테고리의 다른 글

티스토리툴바

[6] 스택 ⑦ 스택의 응용 : 후위수식 변환

[ 문제 2 ] 후위로 변환된 수식을 입력받아 스택을 사용하여 계산한 후 결과 값을 출력하는 프로 그램을 작성하시오

정답 코드 파일

문제 풀이 [1] : 전역 변수 사용

헤더 선언

push 함수 / pop 함수

order 함수 : 연산자의 우선 순위 반환

evaluate 함수

main 함수

헤더 및 구조체 선언

push 함수 / pop 함수

order 함수 : 연산자의 우선 순위 반환

calaulate 함수

main 함수

정답 코드[2]

'Datastructure > [6] 스택' 카테고리의 다른 글

'Datastructure/[6] 스택' 관련글

티스토리툴바