SPOJ 4 - ONP - Transform the Expression
Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).
Input
t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]Text grouped in [ ] does not appear in the input file.
Output
The expressions in RPN form, one per line.Example
Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
Output:
abc*+
ab+zx+*
at+bac++cd+^*Solution
Standard transformation from infix-expression to postfix-express.
Source Code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// #define __DEBUG__
struct char_node {
char character;
struct char_node *next;
};
struct char_node *new_char_node(char character) {
struct char_node *node = (struct char_node*) malloc(sizeof(struct char_node));
node->character = character;
node->next = NULL;
return node;
}
struct char_sequence {
struct char_node *first;
struct char_node *last;
};
struct char_sequence *new_char_sequence(char character) {
struct char_node *node = new_char_node(character);
struct char_sequence *sequence = (struct char_sequence*) malloc(sizeof(struct char_sequence));
sequence->first = node;
sequence->last = node;
return sequence;
}
struct char_sequence *concat_char_sequence(struct char_sequence *a, struct char_sequence *b) {
if (NULL == a) {
return b;
}
if (NULL == b) {
return a;
}
a->last->next = b->first;
a->last = b->last;
free(b);
return a;
}
void print_char_sequence(struct char_sequence *sequence) {
struct char_node *ptr;
if (NULL != sequence) {
for (ptr = sequence->first; ptr != NULL; ptr = ptr->next) {
putchar(ptr->character);
}
}
putchar('\n');
}
struct char_sequence *destroy_char_sequence(struct char_sequence *sequence) {
struct char_node *ptr;
if (NULL != sequence) {
while (sequence->first != NULL) {
ptr = sequence->first;
sequence->first = sequence->first->next;
free(ptr);
}
}
return NULL;
}
struct char_stack {
struct char_stack *prev;
char character;
};
struct char_stack *new_char_stack(char character) {
struct char_stack *stack = (struct char_stack*) malloc(sizeof(struct char_stack));
stack->prev = NULL;
stack->character = character;
return stack;
}
char top_char_stack(struct char_stack *stack) {
return NULL == stack ? EOF : stack->character;
}
struct char_stack *push_char_stack(struct char_stack *stack, char character) {
struct char_stack *top = (struct char_stack*) malloc(sizeof(struct char_stack));
top->prev = stack;
top->character = character;
#ifdef __DEBUG__
printf("[OPERATOR] [PUSH] %c\n", character);
#endif
return top;
}
struct char_stack *pop_char_stack(struct char_stack *stack, char *character) {
if (NULL == stack) {
*character = EOF;
#ifdef __DEBUG__
printf("[OPERATOR] [POP] EOF\n");
#endif
return NULL;
}
*character = stack->character;
#ifdef __DEBUG__
printf("[OPERATOR] [POP] %c\n", *character);
#endif
struct char_stack *top = stack->prev;
free(stack);
return top;
}
struct char_stack *destroy_char_stack(struct char_stack *stack) {
struct char_stack *top;
while (stack != NULL) {
top = stack->prev;
free(stack);
stack = top;
}
return NULL;
}
struct char_sequence_stack {
struct char_sequence_stack *prev;
struct char_sequence *sequence;
};
struct char_sequence *top_char_sequence_stack(struct char_sequence_stack *stack) {
return NULL == stack ? NULL : stack->sequence;
}
struct char_sequence_stack *pop_char_sequence_stack(struct char_sequence_stack *stack,
struct char_sequence **sequence) {
if (NULL == stack) {
*sequence = NULL;
#ifdef __DEBUG__
printf("[OPERAND] [POP] NULL\n");
#endif
return NULL;
}
*sequence = stack->sequence;
#ifdef __DEBUG__
printf("[OPERAND] [POP] ");
print_char_sequence(*sequence);
#endif
struct char_sequence_stack *top = stack->prev;
free(stack);
return top;
}
struct char_sequence_stack *push_char_sequence_stack(struct char_sequence_stack *stack,
struct char_sequence *sequence) {
struct char_sequence_stack *top =
(struct char_sequence_stack*) malloc(sizeof(struct char_sequence_stack));
top->prev = stack;
top->sequence = sequence;
#ifdef __DEBUG__
printf("[OPERAND] [PUSH] ");
print_char_sequence(sequence);
#endif
return top;
}
struct char_sequence_stack *destroy_char_sequence_stack(struct char_sequence_stack *stack) {
struct char_sequence_stack *top;
while (stack != NULL) {
top = stack->prev;
destroy_char_sequence(stack->sequence);
free(stack);
stack = top;
}
return NULL;
}
int priority_of(char operator) {
switch(operator) {
case '^':
return 5;
case '*':
case '/':
return 4;
case '+':
case '-':
return 3;
case ')':
return 2;
case '(':
return 1;
}
return 0;
}
int main(int argc, char **argv) {
int t;
char character, operator;
struct char_stack *operator_stack = NULL;
struct char_sequence_stack *operand_stack = NULL;
struct char_sequence *a, *b;
scanf("%d", &t);
getchar();
while(t--) {
while ((character = getchar()) != '\n' && (character != EOF)) {
switch (character) {
case '(':
operator_stack = push_char_stack(operator_stack, character);
break;
case '+':
case '-':
case '*':
case '/':
case '^':
case ')':
while (priority_of(top_char_stack(operator_stack)) >= priority_of(character)) {
operator_stack = pop_char_stack(operator_stack, &operator);
operand_stack = pop_char_sequence_stack(operand_stack, &b);
operand_stack = pop_char_sequence_stack(operand_stack, &a);
operand_stack = push_char_sequence_stack(operand_stack,
concat_char_sequence(concat_char_sequence(a, b),
new_char_sequence(operator)));
}
if (')' == character) {
operator_stack = pop_char_stack(operator_stack, &operator);
} else {
operator_stack = push_char_stack(operator_stack, character);
}
break;
default:
if (character >= 'a' && character <= 'z') {
operand_stack = push_char_sequence_stack(operand_stack, new_char_sequence(character));
}
}
}
print_char_sequence(top_char_sequence_stack(operand_stack));
operator_stack = destroy_char_stack(operator_stack);
operand_stack = destroy_char_sequence_stack(operand_stack);
}
return 0;
}