#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_EXPR_SIZE 80
typedef struct node *treePointer;
typedef struct node {
char data;
treePointer leftChild, rightChild;
}node;
typedef struct stack *stackPointer;
typedef struct stack {
treePointer data;
stackPointer link;
}stack;
typedef enum {
plus, minus, times, divide, mod, eos, operand
} precedence;
precedence getToken(char *symbol, int *n);
void push(treePointer temp);
treePointer pop();
void stackEmpty();
void inorder(treePointer node);
char expr[MAX_EXPR_SIZE];
stackPointer top = NULL;
int main() {
printf("the length of string should be less than 80\n");
FILE* f = fopen("input.txt", "r");
if (!f) {
fprintf(stderr, "file doesn't exist\n");
exit(EXIT_FAILURE);
}
fgets(expr, sizeof(expr), f);
printf("input string (postfix expression) : %s\n", expr);
printf("creating its binary tree\n\n");
treePointer root = NULL, temp;
char symbol;
precedence token;
int n = 0;
for (token = getToken(&symbol, &n);token != eos;token = getToken(&symbol, &n)) {
if (token == operand) {
temp = (treePointer)malloc(sizeof(*temp));
temp->data = symbol;temp->leftChild = temp->rightChild = NULL;
push(temp);
}
else if (token != eos) {
temp = (treePointer)malloc(sizeof(*temp));
temp->data = symbol;
temp->rightChild = pop();
temp->leftChild = pop();
push(temp);
}
root = top->data;
}
printf("iterative inorder travelsal : ");
inorder(root);
}
precedence getToken(char *symbol, int *n) {
*symbol = expr[(*n)++];
switch (*symbol) {
case '+': return plus;
case '-': return minus;
case '*': return times;
case '/': return divide;
case '%': return mod;
case '\0': return eos;
default: return operand;
}
}
void push(treePointer temp) {
stackPointer stemp = (stackPointer)malloc(sizeof(*stemp));
stemp->data = temp;stemp->link = NULL;
if (top)
stemp->link = top;
top = stemp;
}
treePointer pop() {
if (!top)
stackEmpty();
stackPointer stemp = top;
treePointer ttemp = top->data;
top = top->link;
free(stemp);
return ttemp;
}
void stackEmpty() {
fprintf(stderr, "stack is empty\n");
exit(EXIT_FAILURE);
}
void inorder(treePointer node) {
top = NULL;
for (;;) {
for (;node;node = node->leftChild)
push(node);
node = pop();
if (!node) break;
printf("%c", node->data);
node = node->rightChild;
}
}
input.txt에는 AB/C*D*E+처럼 postfix 수식 들어가있고 트리만들어서 inorder방식으로 출력해서 infix 수식으로 출력하는건데 inorder함수에서 스택 pop한뒤에 if로 노드 없으면 브레이크되게 해봤는데 그전에 pop하는과정에서 이미 스택이 비어있어서 stackEmpty함수가 실행되서 그대로 종료되버림 종료안되게끔 하고싶은데 방법없을까? stackEmpty함수를 없애면 되지 않을까 싶어서 없애봤는데 어차피 이미 스택 비어있어서 오류코드 리턴하면서 종료됏음..
댓글 0