When we have the expression a + b, we know the meaning that we should add a and b together. This form is called infix. Another form is postfix, which will look like a b +. So why do we need a postfix form? Postfix forms do not have ambiguity. For example,a + b * c we do not know which operation should evaluate first. To remove the ambiguity, we use parentheses (a + b) * c, but there is no problem in the postfix form a b + c *.
How to convert infix to postfix
The algorithm for converting infix to postfix is as follows. which can handle mathematical expressions like this (a + b) * c / sqr(c) + pow(2, 3) - max(d, e).
1. Loop through the sequence of infix strings
2. for each token
- if toke is operand, append token to postfix string
- if token == '(' push token in stack
- if token == ')' pop token from the stack and append to postfix string until find ')' token. Token ')' is removed from the stack.
- if token == ',' pop token from the stack and append to postfix string until find '(' token. Token ')' still in the stack.
- if token is a unary operator, append the token to the postfix string.
- else compare token with top of the stack and pop a token from stack, then append to the postfix string until the precedence of operator of top of the stack is greater than the token. Then push the token to the stack.
3. Pop an operator from the stack and append to the postfix string until the stack is empty.
Implementation
You can either use the built-in stack from C++ or implement it yourself.
// infix_to_postfix.c
typedef struct _stack {
int top;
int cap;
void **data;
} _stack;
static _stack make_stack(int cap);
static void free_stack(_stack *s);
static void stack_push(_stack *s, void *v);
static void *stack_pop(_stack *s);
static void *stack_peek(_stack *s);
static bool stack_is_empty(_stack *s);
lex_data **infix_to_postfix(lex_data *infix, int size_in, int *size_out) {
lex_data **postfix;
_stack s = make_stack(size_in);
int len = 0;
lex_data *l;
lex_data *o;
postfix = (lex_data**) malloc(size_in * sizeof(lex_data**));
for (int i = 0; i < size_in; i++) {
l = &infix[i];
if (l->token_code == MATH_SPACE) continue;
if (is_operand(l->token_code)) {
postfix[len++] = l;
} else if (l->token_code == MATH_BRACKET_START) {
stack_push(&s, (void *) l);
} else if (l->token_code == MATH_BRACKET_END) {
while (1) {
o = (lex_data*) stack_pop(&s);
if (o->token_code == MATH_BRACKET_START) {
break;
}
postfix[len++] = o;
}
} else if (l->token_code == MATH_COMMA) {
while (!stack_is_empty(&s) && ((lex_data*) stack_peek(&s))->token_code != MATH_BRACKET_START) {
postfix[len++] = (lex_data*) stack_pop(&s);
}
}else {
if (!is_unary_op(l->token_code)) {
while (!stack_is_empty(&s) && precedent(l->token_code) <= precedent(((lex_data*) stack_peek(&s))->token_code)) {
postfix[len++] = (lex_data*) stack_pop(&s);
}
}
stack_push(&s, l);
}
}
while (!stack_is_empty(&s)) {
postfix[len++] = (lex_data*) stack_pop(&s);
}
free_stack(&s);
*size_out = len;
return postfix;
}
_stack make_stack(int cap) {
_stack s = {.top = -1, .cap = cap};
s.data = (void**) malloc(cap * sizeof(void*));
return s;
}
void free_stack(_stack *s) {
assert(s);
free(s->data);
s->data = NULL;
}
void stack_push(_stack *s, void *v) {
assert(s && s->top + 1 < s->cap);
s->data[++s->top] = v;
}
void *stack_pop(_stack *s) {
assert(s && s->top > -1);
return s->data[s->top--];
}
void *stack_peek(_stack *s) {
assert(s && s->top > -1);
return s->data[s->top];
}
bool stack_is_empty(_stack *s) {
assert(s);
return s->top == -1;
}
Testing the infix_to_postfix implementation
You can test your implementation as follows
// infix_to_postfix_test.c
#include <stdio.h>
#include "parser_export.h"
#include "math_expr_tree.h"
#include "dtype.h"
#include <assert.h>
extern lex_data **infix_to_postfix(lex_data *infix, int size_in, int *size_out);
#define DO_TEST(infix_array) { \
int n; \
int len; \
lex_data **postfix; \
n = sizeof(infix_array)/sizeof(infix_array[0]); \
printf("---\n"); \
for (int i = 0; i < n; i++) { \
printf("%s", infix_array[i].text); \
} \
printf("\n"); \
postfix = infix_to_postfix(infix_array, n, &len); \
for (int i = 0; i < len; i++) { \
printf("%s ", postfix[i]->text); \
} \
printf("\n"); \
} \
}
int main(void) {
// a + b * c
lex_data infix_array1[] = {
{MATH_IDENTIFIER, 1, "a" },
{MATH_SPACE, 1, " " },
{MATH_PLUS, 1, "+" },
{MATH_SPACE, 1, " " },
{MATH_IDENTIFIER, 1, "b" },
{MATH_SPACE, 1, " " },
{MATH_MUL, 1, "*" },
{MATH_SPACE, 1, " " },
{MATH_IDENTIFIER, 1, "c" },
};
// max(a, b)
lex_data infix_array2[] = {
{MATH_MAX, 3, "max" },
{MATH_BRACKET_START, 1, "(" },
{MATH_IDENTIFIER, 1, "a" },
{MATH_COMMA, 1, "," },
{MATH_SPACE, 1, " " },
{MATH_IDENTIFIER, 1, "b" },
{MATH_BRACKET_END, 1, ")" },
};
// a + sqr(b) * sqrt(c) + pow(d,e)
lex_data infix_array3[] = {
{MATH_IDENTIFIER, 1, "a" },
{MATH_PLUS, 1, "+" },
{MATH_SQR, 3, "sqr" },
{MATH_BRACKET_START, 1, "(" },
{MATH_IDENTIFIER, 1, "b" },
{MATH_BRACKET_END, 1, ")" },
{MATH_MUL, 1, "*" },
{MATH_SQRT, 4, "sqrt" },
{MATH_BRACKET_START, 1, "(" },
{MATH_IDENTIFIER, 1, "c" },
{MATH_BRACKET_END, 1, ")" },
{MATH_PLUS, 1, "+" },
{MATH_POW, 3, "pow" },
{MATH_BRACKET_START, 1, "(" },
{MATH_IDENTIFIER, 1, "d" },
{MATH_COMMA, 1, "," },
{MATH_IDENTIFIER, 1, "e" },
{MATH_BRACKET_END, 1, ")" },
};
// a + sqr(max(b,c,d)) - e
lex_data infix_array4[] = {
{MATH_IDENTIFIER, 1, "a" },
{MATH_PLUS, 1, "+" },
{MATH_SQR, 3, "sqr" },
{MATH_BRACKET_START, 1, "(" },
{MATH_MAX, 3, "max"},
{MATH_BRACKET_START, 1, "(" },
{MATH_IDENTIFIER, 1, "b" },
{MATH_COMMA, 1, "," },
{MATH_IDENTIFIER, 1, "c" },
{MATH_COMMA, 1, "," },
{MATH_IDENTIFIER, 1, "d" },
{MATH_BRACKET_END, 1, ")" },
{MATH_BRACKET_END, 1, ")" },
{MATH_MINUS, 1, "-"},
{MATH_IDENTIFIER, 1, "e" },
};
DO_TEST(infix_array1);
DO_TEST(infix_array2);
DO_TEST(infix_array3);
DO_TEST(infix_array4);
}
Top comments (0)