์ค์ ํ๊ธฐ๋ฒ์ด๋? ์ผ๋ฐ์ ์ผ๋ก ์ฌ๋์ด ์์์ ํ๊ธฐํ ๋ ์ฌ์ฉํ๋ ํ๊ธฐ ๋ฐฉ๋ฒ. ์์) 7 * 5 + 3
ํ์ ํ๊ธฐ๋ฒ์ด๋? ์ปดํจํฐ๊ฐ ๊ณ์ฐํ๊ธฐ์ ํธํ ์์์ ํํ. ํ์ ํ๊ธฐ๋ฒ์์ ์ฐ์ฐ์๋ ๋ค์ชฝ์ ์์น. ์์) 7 5 * 3 +
1) ์ผ๋ฐ์ ์ผ๋ก ์ฌ๋์ด ์์์ ํ๊ธฐํ ๋ ์ฌ์ฉํ๋ ํ๊ธฐ ๋ฐฉ๋ฒ
1) ์ปดํจํฐ๊ฐ ๊ณ์ฐํ๊ธฐ์ ํธํ ์์์ ํํ
2) ํ์ ํ๊ธฐ๋ฒ์์ ์ฐ์ฐ์๋ ๋ค์ชฝ์ ์์น
1) ์์์ ํ์ ํ๊ธฐ๋ฒ์ผ๋ก ๋ณํ
2) ํ์ ํ๊ธฐ๋ฒ์ ๊ณ์ฐํ์ฌ ๊ฒฐ๊ณผ ๋์ถ
1) ์คํ ๊ตฌํ
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // ๋ฌธ์์ด ์ฒ๋ฆฌ๋ฅผ ์ํด
#define INF 99999999
typedef struct { // ๊ตฌ์กฐ์ฒด ์ ์
char data[100];
struct Node *next; // ๋ค์ ๋
ธ๋๋ก ์ฐ๊ฒฐํ๊ธฐ ์ํด ์ ์ธ
} Node;
typedef struct {
Node *top; // top pointer ์ ์ธ
} Stack;
2) ์คํ ํจ์ ๊ตฌํ
void push(Stack *stack, char *data) {
Node *node = (Node*)malloc(sizeof(Node));
strcpy(node->data, data);
node->next = stack->top;
stack->top = node;
}
char* getTop(Stack *stack) {
Node *top = stack->top;
return top->data;
}
char* pop(Stack *stack) {
if (stack->top == NULL) {
printf("์คํ ์ธ๋ํ๋ก์ฐ๊ฐ ๋ฐ์ํ์ต๋๋ค.\n");
return -INF;
}
Node *node = stack->top;
char *data = (char*)malloc(sizeof(char) * 100);
strcpy(data, node->data);
stack->top = node->next;
free(node);
return data;
}
1) ํผ์ฐ์ฐ์๊ฐ ๋ค์ด์ค๋ฉด ๋ฐ๋ก ์ถ๋ ฅ
2) ์ฐ์ฐ์๊ฐ ๋ค์ด์ค๋ฉด ์๊ธฐ๋ณด๋ค ์ฐ์ ์์๊ฐ ๋๊ฑฐ๋ ๊ฐ์ ๊ฒ๋ค์ ๋นผ๊ณ ์์ ์ ์คํ์ ๋ด๊ธฐ
3) ์ฌ๋ ๊ดํธ (
๋ฅผ ๋ง๋๋ฉด ๋ฌด์กฐ๊ฑด ์คํ์ ๋ด๊ธฐ
4) ๋ซ๋ ๊ดํธ )
๋ฅผ ๋ง๋๋ฉด (
๋ฅผ ๋ง๋ ๋๊น์ง ์คํ์์ ์ถ๋ ฅ
3) ํ์ ํ๊ธฐ๋ฒ์ผ๋ก ๋ณํ:: ์ฐ์ ์์ ํจ์ ๋ง๋ค๊ธฐ
int getPriority(char *i) {
if (!strcmp(i, "(")) return 0;
if (!strcmp(i, "+") || !strcmp(i, "-")) return 1;
if (!strcmp(i, "*") || !strcmp(i, "/")) return 2; return 3;
}
4) ํ์ ํ๊ธฐ๋ฒ์ผ๋ก ๋ณํ:: ๋ณํ ํจ์ ๋ง๋ค๊ธฐ
char* transition(Stack *stack, char **s, int size) {
char res[1000] = "";
for (int i = 0; i < size; i++) {
if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
while (stack->top != NULL && getPriority(getTop(stack)) >= getPriority(s[i])) {
strcat(res, pop(stack)); strcat(res, " ");
}
push(stack, s[i]);
}
else if (!strcmp(s[i], "(")) push(stack, s[i]);
else if (!strcmp(s[i], ")")) {
while (strcmp(getTop(stack), "(")) {
strcat(res, pop(stack)); strcat(res, " ");
}
pop(stack);
}
else strcat(res, s[i]); strcat(res, " ");
}
while (stack->top != NULL) {
strcat(res, pop(stack)); strcat(res, " ");
}
return res;
}
1) ํผ์ฐ์ฐ์๊ฐ ๋ค์ด์ค๋ฉด ์คํ์ ๋ด๊ธฐ
2) ์ฐ์ฐ์๋ฅผ ๋ง๋๋ฉด ์คํ์์ ๋ ๊ฐ์ ์ฐ์ฐ์๋ฅผ ๊บผ๋ด์ ์ฐ์ฐํ ๋ค์ ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ์คํ์ ๋ด๊ธฐ
3) ์ฐ์ฐ์ ๋ง์น ๋ค์ ์คํ์ ๋จ์์๋ ํ๋์ ํผ์ฐ์ฐ์๊ฐ ์ฐ์ฐ ์ํ ๊ฒฐ๊ณผ
5) ํ์ ํ๊ธฐ๋ฒ ๊ณ์ฐ
void calculate(Stack *stack, char **s, int size) {
int x, y, z;
for (int i = 0; i < size; i++) {
if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
x = atoi(pop(stack));
y = atoi(pop(stack));
if (!strcmp(s[i],
if (!strcmp(s[i],
if (!strcmp(s[i],
if (!strcmp(s[i],
char buffer[100];
sprintf(buffer, "%d", z);
push(stack, buffer);
} else {
push(stack, s[i]);
}
}
printf("%s ", pop(stack));
}
6) ๋ง๋ค์ด์ง ๊ณ์ฐ๊ธฐ ์ฌ์ฉํ๊ธฐ 1
int main(void) {
Stack stack;
stack.top = NULL;
char a[100] = "( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";
int size = 1;
for (int i = 0; i < strlen(a); i++) {
if (a[i] == ' ') size++;
}
char *ptr = strtok(a, " ");
char **input = (char**)malloc(sizeof(char*) * size);
for (int i = 0; i < size; i++) {
input[i] = (char*)malloc(sizeof(char) * 100);
}
for (int i = 0; i < size; i++) {
strcpy(input[i], ptr);
ptr = strtok(NULL, " ");
}
char b[1000] = "";
strcpy(b, transition(&stack, input, size));
printf("ํ์ ํ๊ธฐ๋ฒ: %s\n", b); system("pause");
return 0;
}
6) ๋ง๋ค์ด์ง ๊ณ์ฐ๊ธฐ ์ฌ์ฉํ๊ธฐ 2
size = 1;
for (int i = 0; i < strlen(b) - 1; i++) { // ๋ง์ง๋ง์ ํญ์ ๊ณต๋ฐฑ์ด ๋ค์ด๊ฐ๋ฏ๋ก 1์ ๋นผ๊ธฐ
if (b[i] == ' ') size++;
}
char *ptr2 = strtok(b, " ");
for (int i = 0; i < size; i++) {
strcpy(input[i], ptr2);
ptr2 = strtok(NULL, " ");
}
calculate(&stack, input, size);
system("pause");
return 0;