0x 00 데이터 구조 - C 언어 구현 (스 택 + 접미사 식 계산)

/*
  （tack）                    ，        ，     （top）。
         Push（  ） Pop（  ）。

 Functions:
 （              ）
          
         
         
          
     push    
     pop  
         Top  
        ，    ，     
      

*/

#ifndef STACK_H
#define STACK_H


#define MAXLEN 100
typedef enum {
    false = 0,
    true
} BOOL;

//    。
struct node;
typedef struct node node;
typedef struct node *to_node;
typedef to_node pos;

struct stack_node;
typedef struct stack_node stack_node;
typedef stack_node *stack;


//      
stack create_stack(void);

//     
BOOL set_empty(stack s);

//     
int calc_length(stack s);


// push    
int push(stack s, int x);

// pop  
int pop(stack s);

//     Top  
int get_val(stack s);

//    ，    ，     
BOOL is_empty(stack s);

//  
void output(stack s);

#endif

#include "stack.h"
#include 
#include 


/*
struct node;
typedef struct node node;
typedef struct node *to_node;
typedef to_node pos;

struct stack_node;
typedef struct stack_node stack_node;
typedef stack_node *stack;
*/
struct node {
    int val;
    struct node *next;
};
struct stack_node {
    int capacity;
    struct node *top;
};
/*
           ，             ，       （       ）
*/
//      
stack create_stack(void)
{
    stack tmp = (stack)malloc(sizeof(stack_node));
    if(tmp != NULL) {
        tmp->top = NULL;
        tmp->capacity = 0;
    }
    return tmp;
}

//     
BOOL set_empty(stack s)
{
    pos tmp;
    while(s->capacity != 0) {
        tmp = s->top;
        s->top = tmp->next;
        free(tmp);
        (s->capacity)--;
    }
    return true;
}

//     
int calc_length(stack s)
{
    return s->capacity;
}


// push    
int push(stack s, int x)
{
    node *tmp = (node *)malloc(sizeof(node));
    tmp->val = x;
    tmp->next = s->top;
    s->top = tmp;
    (s->capacity)++;
    return x;
}

// pop  
int pop(stack s)
{
    node *tmp;
    int r = 0;
    tmp = s->top;
    s->top = tmp->next;
    (s->capacity)--;
    r = tmp->val;
    free(tmp);
    return r;
}

//     Top  
int get_val(stack s)
{
    return s->top->val;
}

//    ，    ，     
BOOL is_empty(stack s)
{
    return (s->capacity == 0);
}

//  
void output(stack s)
{
    pos tmp = s->top;
    while(tmp != NULL) {
        printf("%d->", tmp->val);
        tmp = tmp->next;
    }
    printf("|
");
}

#include 
#include 
#include 
#include 
#include "stack.h"


int main()
{
//          

    stack s;
    int i = 0, len = 0;
    int tmp1, tmp2;
    int op;
//  char in[100] = {0};
    char in[] = {'6','5','2','3','+','8','*','+','3','+','*'};
    s = create_stack();
//  while((in[i] = getchar())!=EOF) {
//      i++;
//  }

    len = strlen(in);

    for(i = 0; iif(tmp1=='+' || tmp1=='-' || tmp1 == '*' || tmp1 == '/') {
            op = tmp1;
            tmp1 = pop(s);
            tmp2 = pop(s);
            switch(op) {
                case '+': push(s, tmp1+tmp2);break;
                case '-': push(s, tmp1-tmp2);break;
                case '*': push(s, tmp1*tmp2);break;
                case '/': push(s, tmp1/tmp2);break;
                default: break;
            }
        } else if(isdigit(tmp1)) {
            push(s,tmp1-48);
        }
        output(s);
    }

    output(s);
    return 0;
}

6->|
5->6->|
2->5->6->|
3->2->5->6->|
5->5->6->|
8->5->5->6->|
40->5->6->|
45->6->|
3->45->6->|
48->6->|
288->|
288->|
Time elapsed: 000:00:047
Press any key to continue