13 - Ejemplo práctico 4: parser infijo → postfijo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 256

typedef struct {
  char datos[MAX][32];
  int top;
} StackStr;

typedef struct {
  double datos[MAX];
  int top;
} StackNum;

void push_str(StackStr *s, const char *token) {
  strcpy(s->datos[s->top++], token);
}

char *peek_str(StackStr *s) {
  return s->top == 0 ? NULL : s->datos[s->top - 1];
}

char *pop_str(StackStr *s) {
  return s->top == 0 ? NULL : s->datos[--s->top];
}

void push_num(StackNum *s, double val) {
  s->datos[s->top++] = val;
}

double pop_num(StackNum *s) {
  return s->top == 0 ? 0 : s->datos[--s->top];
}

int es_op(const char *t) {
  return strcmp(t, "+") == 0 || strcmp(t, "-") == 0 ||
         strcmp(t, "*") == 0 || strcmp(t, "/") == 0;
}

int prec(const char *t) {
  if (strcmp(t, "+") == 0 || strcmp(t, "-") == 0) return 1;
  if (strcmp(t, "*") == 0 || strcmp(t, "/") == 0) return 2;
  return 0;
}

void infijo_a_postfijo(const char *entrada, char salida[][32], int *sal_len) {
  StackStr ops = {.top = 0};
  char buffer[32];
  const char *ptr = entrada;
  *sal_len = 0;

  while (sscanf(ptr, "%31s", buffer) == 1) {
    ptr = strstr(ptr, buffer) + strlen(buffer);
    if (isdigit(buffer[0])) {
      strcpy(salida[(*sal_len)++], buffer);
    } else if (strcmp(buffer, "(") == 0) {
      push_str(&ops, buffer);
    } else if (strcmp(buffer, ")") == 0) {
      while (ops.top && strcmp(peek_str(&ops), "(") != 0) {
        strcpy(salida[(*sal_len)++], pop_str(&ops));
      }
      pop_str(&ops);
    } else if (es_op(buffer)) {
      while (ops.top && prec(peek_str(&ops)) >= prec(buffer)) {
        strcpy(salida[(*sal_len)++], pop_str(&ops));
      }
      push_str(&ops, buffer);
    }
  }
  while (ops.top) {
    strcpy(salida[(*sal_len)++], pop_str(&ops));
  }
}

double evaluar_postfija(char tokens[][32], int len) {
  StackNum valores = {.top = 0};
  for (int i = 0; i < len; ++i) {
    if (!es_op(tokens[i])) {
      push_num(&valores, atof(tokens[i]));
    } else {
      double b = pop_num(&valores);
      double a = pop_num(&valores);
      if (strcmp(tokens[i], "+") == 0) push_num(&valores, a + b);
      else if (strcmp(tokens[i], "-") == 0) push_num(&valores, a - b);
      else if (strcmp(tokens[i], "*") == 0) push_num(&valores, a * b);
      else if (strcmp(tokens[i], "/") == 0) push_num(&valores, a / b);
    }
  }
  return pop_num(&valores);
}

int main(void) {
  const char *expr = "3 + 4 * 2 / ( 1 - 5 )";
  char postfija[MAX][32];
  int len = 0;
  infijo_a_postfijo(expr, postfija, &len);
  printf("Postfija: ");
  for (int i = 0; i < len; ++i) printf("%s ", postfija[i]);
  printf("\nResultado: %.2f\n", evaluar_postfija(postfija, len));
  return 0;
}