infix_to_postfix.c

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

typedef struct Node
{
  int value;
  struct Node* next;
} Node;

typedef struct Stack
{
  Node* top;
} Stack;

void push(Stack** s, int value);
char pop(Stack** s);
int empty(Stack* s);
char get_op(Stack** s);
void infix_to_postfix(char infix[], char postfix[]);
int reduce_postfix(char postfix[]);
void in_stack(Stack* s);

int main(int argc, char *argv[])
{
  char bt_postfix[100] = "";
  char bt_infix[100] = "(";
  scanf("%s", &bt_infix[1]);
  size_t len = strlen(bt_infix);
  bt_infix[len] = ')';
  bt_infix[len + 1] = '\0';

  infix_to_postfix(bt_infix, bt_postfix);

  printf("%s\n", bt_postfix);

  printf("Ket qua phep toan: %d\n", reduce_postfix(bt_postfix));

  return 0;
}

void push(Stack** s, int value)
{
  Node* new_node = malloc(sizeof(Node));
  new_node->value = value;

  if (*s == NULL)
  {
    *s = malloc(sizeof(Stack));
    (*s)->top = new_node;
    return;
  }

  new_node->next = (*s)->top;
  (*s)->top = new_node;
}

char pop(Stack** s)
{
  if (*s == NULL)
  {
    return 0;
  }

  Node* top = (*s)->top;
  (*s)->top = top->next;
  char x = top->value;
  free(top);

  return x;
}

char get_op(Stack** s)
{
  char ret = 0;
  if (*s == NULL)
  {
    return 0;
  }

  Node* prev = NULL;
  Node* node = (*s)->top;

  while (node != NULL)
  {
    if (node->value == '(')
    {
      return 0;
    }

    if (node->value == '/' ||
        node->value == '*' ||
        node->value == '+' ||
        node->value == '-')
    {
      break;
    }
    prev = node;
    node = node->next;
  }

  if (node == NULL)
  {
    return 0;
  }
  ret = node->value;

  if (prev == NULL)
  {
    (*s)->top = node->next;
  }
  else
  {
    prev->next = node->next;
  }

  free(node);
  return ret;
}

int empty(Stack* s)
{
  if (s == NULL)
  {
    return 0;
  }

  return s->top == NULL;
}

void infix_to_postfix(char infix[], char postfix[])
{
  Stack* S = NULL;

  for (size_t i = 0; i < strlen(infix); ++i) {
    char c = infix[i];
    switch (c) {
    case '(':
      push(&S, c);
      break;
    case ')': {
      while (!empty(S))
      {
        char top = pop(&S);
        if (top == '(') break;

        strncat(postfix, &top, 1);
      }
      break;
    }
    case '+':
    case '-': {
      while (1)
      {
        char c_x = get_op(&S);

        if (c_x == 0)
        {
          break;
        }

        strncat(postfix, &c_x, 1);
      }
    }
    case '/':
    case '*':
      push(&S, c);
      break;
    default:
      strncat(postfix, &c, 1);
      break;
    }
    printf("---------------\n");
    printf("Op: %c\n", c);
    printf("Stack: ");
    in_stack(S);
    printf("Infix: %s\n", postfix);
  }
}

int reduce_postfix(char postfix[])
{
  Stack* S = NULL;

  for (size_t i = 0; i < strlen(postfix); ++i) {
    char c = postfix[i];
    switch (c) {
    case '+': {
      int y = pop(&S);
      int x = pop(&S);

      push(&S, x + y);
      break;
    }
    case '-': {
      int y = pop(&S);
      int x = pop(&S);

      push(&S, x - y);
      break;
    }
    case '/': {
      int y = pop(&S);
      int x = pop(&S);

      push(&S, x / y);
      break;
    }
    case '*': {
      int y = pop(&S);
      int x = pop(&S);

      push(&S, x * y);
      break;
    }
    default:
      push(&S, c - '0');
      break;
    }
  }

  return pop(&S);
}

void in_stack(Stack* s)
{
  Node* node = s->top;

  while (node != NULL)
  {
    printf("%c", node->value);
    node = node->next;
  }
  printf("\n");
}