#include <stdio.h>
#include <stdlib.h>
#define MAX_INDEX 100 // 상수 선언.
typedef struct { //stack 구조체를 생성한다.
int data[MAX_INDEX]; // MAX_INDEX 의 크기를 가진 멤버 data 배열을 선언한다.
int top; // data 배열의 현재 인덱스를 나타내는 멤버 top 을 선언한다.
}stack;
int is_full(stack s) { //스택이 가득찼나 "검사" 하는 함수
return (s.top == MAX_INDEX - 1); // top 변수가 99일때 1을 반환한다.(true 반환)
}
int is_empty(stack s) { //스택이 비워졌나 검사하는 함수
return (s.top == -1); //top 변수가 -1일때 1을 반환한다.(true 반환)
}
void push(stack* s, int input) { //스택에 값을 넣는 함수, 받아온 input 을 스택에 넣는 함수다.
if (is_full(*s)) { //만약 스택이 가득 찼으면
printf("스택이 가득 찼음"); // 이것을 출력하고
exit(1); // 프로그램을 종료한다.
}
else { //만약 스택이 가득 차지 않았으면
s->top += 1; // 변수 top은 1을 증가한다.
s->data[s->top] = input; //data 배열에 증가한 top index 에 input 을 할당한다.
}
}
void init(stack* s) { // 스택의 인덱스 위치를 초기화하는 함수, 스택이 생성되면 무조건 호출해야함
s->top = -1;
}
int peek(stack s) { //배열이 비어있지않으면 배열의 top index의 값을 반환한다.
//마지막으로 push 값을 반환한다.
if (is_empty(s)) { //만약 스택이 비워져있다면
printf("스택이 비어있음!"); // 이것을 출력하고
exit(1); // 프로그램 종료
}
else { // 만약 스택이 비워져있는게 아니라면
return (s.data[s.top]); // data 배열의 top index의 값을 반환한다.
}
}
int pop(stack* s) { // data배열의 top index 를 -1 을 하고 출력은 top index의 값을 한다.
//마지막으로 push 값을 삭제하고 반환한다.
if (is_empty(*s)) { //만약 스택이 비워져있다면
printf("스택이 비어있음!");// 이것을 출력하고
exit(1);// 프로그램 종료
}
else { // 만약 스택이 비워져있는게 아니라면
s->top -= 1; //top변수에 -1을 빼고
return (s->data[s->top + 1]); // 반환은 data배열의 top변수 +1 index를 반환한다.
}
}
int main() {
/*
문제 :
후위식 평가를 먼저 한다!
입력 : 56*2-
출력 : 28
*/
stack st;
init(&st);
char string[] = "56*2-";
//숫자가 들어오면 ? > 스택에 무조건 push
//연산자가 들어오면 ? > 두개 pop 시키고, 연산자에 맞는 계산을 수행하기.
for (int i = 0; string[i] != NULL; i++) { //char string배열의 값을 검사하기 위해 for문을 돌렸어요.
if (string[i] >= '0' && string[i] <= '9') { // 만약 i번째에값이 0~9까지라면 push를 해서 스택 쌓기 해요.
push(&st, string[i] - '0'); // 여기는 char 형은 ascii 코드로 표현되어있기 때문에 그냥 숫자로 바꾸기 위해
// '0' 을 뺀다.
}
else if (string[i] == '+' ) { // 만약 i번째의 값이 '+' 라면
int calculate = pop(&st) + pop(&st); //맨위에 있는 숫자 두개를 꺼내서(pop 두번 수행) 더하기 연산을 한다.
push(&st, calculate); //계산된 숫자를 push한다.
}
else if (string[i] == '-') { // 만약 i번째의 값이 '-' 라면
//먼저 들어간 숫자 - 나중에 들어간 숫자를 수행해야 하므로
int last = pop(&st); // 나중에 들어간 숫자를 last 에 저장하고
int before = pop(&st); // 먼저 들어간 숫자를 before 에 저장하고
int calculate = before - last; // before - last 를 수행한다.
push(&st, calculate); //계산된 숫자를 push한다.
}
else if (string[i] == '/') { // 만약 i번째의 값이 '/' 라면
//먼저 들어간 숫자 / 나중에 들어간 숫자를 수행해야 하므로
int last = pop(&st); // 나중에 들어간 숫자를 last 에 저장하고
int before = pop(&st); // 먼저 들어간 숫자를 before 에 저장하고
int calculate = before / last;// before / last 를 수행한다.
push(&st, calculate);;//계산된 숫자를 push한다.
}
else if (string[i] == '*') { // 만약 i번째의 값이 '*' 라면
int calculate = pop(&st) * pop(&st); //맨위에 있는 숫자 두개를 꺼내서(pop 두번 수행) 곱하기 연산을 한다.
push(&st, calculate);//계산된 숫자를 push한다.
}
}
printf("계산 결과는 %d 입니다", pop(&st)); //계산이 다 끝나면, 스택에 계산 결과가 있으므로 pop 을 하여 출력한다