There has been a question related with prefix to infix/postfix expression on the latest assignment in C. I managed to solve this puzzle, the whole assignment is here and you can take a peek at (Question 2).
The whole resolving idea has been basically expressed in Jim’s description, using a recursive way to build a tree, deal from left leaf to right leaf and printing out from bottom to top. This is code is my original piece, I might have a few presentation errors that not have matched with Jim’s requirements. Anyway, here is the whole code:
/* * File: prefix.c * Author: Luxing Huang * Date: 2013/11/24 * Version: 1.0 * * Purpose: This programme will take in tokens from arguments or stdin to * give back: * 1. postfix polish notation * 2. infix polish notation * 3. the result of the calculation (optional) * * Assumption: User input will not exceed 256/2=128 chars. */ #include#include #include #include #include #include #define LIMIT 257 int pos; typedef struct expression_tree_node { struct expression_tree_node *leftnode; struct expression_tree_node *rightnode; union { int32_t left; char leftop[4]; } left; union { int32_t right; char rightop[4]; } right; union { char topop[4]; int32_t top; } top; bool left_done; bool right_done; } *node_T; /* * Name: convert * Purpose: Convert from prefix expression to infix and postfix expression. * Arguments: prefixin, postout, infixout, leaf1 * Returns: nothing * Modifies: postout, infixout */ void convert(char *prefixin, char *postout, char *infixout, node_T leaf1) { int ret; node_T leaf2 = malloc(sizeof(struct expression_tree_node)); char *tmp = calloc(LIMIT, sizeof(char)); char *postoutl = calloc(LIMIT, sizeof(char)); char *postoutr = calloc(LIMIT, sizeof(char)); char *infixoutl = calloc(LIMIT, sizeof(char)); char *infixoutr = calloc(LIMIT, sizeof(char)); pos = 0; if (tmp == NULL || postoutl == NULL || postoutr == NULL || infixoutl == NULL || infixoutr == NULL) { fprintf(stderr, "Unable to calloc.\n"); exit(-1); } /* Scanning in the top operator */ if (leaf1->top.topop == 0) { ret = sscanf(prefixin, "%s", leaf1->top.topop); if (ret == 0) { fprintf(stderr, "Invalid expression.\n"); exit(-1); } pos+= 2; } /* Scanning left tree */ ret = sscanf(prefixin, "%d", &leaf1->left.left); if (ret == 0) { ret = sscanf(prefixin, "%s", leaf1->left.leftop); if (ret == EOF) { fprintf(stderr, "Insufficient arguments!\n"); exit(-1); } pos += 2; strncpy(leaf2->top.topop, leaf1->left.leftop, sizeof(int32_t)); leaf1->leftnode = leaf2; convert(prefixin + pos, postoutl, infixoutl, leaf2); pos += 2; } else if (ret == EOF) { fprintf(stderr, "Insufficient arguments!\n"); exit(-1); } else { pos += 2; leaf1->left_done = true; } /* Scanning Right tree */ ret = sscanf(prefixin + pos, "%d", &leaf1->right.right); if (ret == 0) { ret = sscanf(prefixin + pos, "%s", leaf1->right.rightop); if (ret == EOF) { fprintf(stderr, "Insufficient arguments!\n"); exit(-1); } pos += 2; strncpy(leaf2->top.topop, leaf1->right.rightop, sizeof(int32_t)); leaf1->rightnode = leaf2; convert(prefixin + pos, postoutr, infixoutr, leaf2); pos += 2; } else if (ret == EOF) { fprintf(stderr, "Insufficient arguments!\n"); exit(-1); } else { leaf1->right_done = true; pos += 2; } /* Setting up Output */ if (leaf1->left_done == true) { if (leaf1->right_done == true) { sprintf(tmp, "%d %d %s ", leaf1->left.left, leaf1->right.right, leaf1->top.topop); strncpy(postout, tmp, LIMIT); sprintf(tmp, "(%d %s %d)", leaf1->left.left, leaf1->top.topop, leaf1->right.right); strncpy(infixout, tmp, LIMIT); } else { sprintf(tmp, "%d %s %s", leaf1->left.left, postoutr, leaf1->top.topop); strncpy(postout, tmp, LIMIT); sprintf(tmp, "(%d %s %s)", leaf1->left.left, leaf1->top.topop, infixoutr); strncpy(infixout, tmp, LIMIT); } } else { if (leaf1->right_done == true) { sprintf(tmp, "%s %d %s", postoutl, leaf1->right.right, leaf1->top.topop); strncpy(postout, tmp, LIMIT); sprintf(tmp, "(%s %s %d)", infixoutl, leaf1->top.topop, leaf1->right.right); strncpy(infixout, tmp, LIMIT); } else { sprintf(tmp, "%s %s %s", postout, postout, leaf1->top.topop); strncpy(postout, tmp, LIMIT); sprintf(tmp, "(%s %s %s)", infixout, leaf1->top.topop, infixout); strncpy(infixout, tmp, LIMIT); } } } int main(int argc, char *argv[]) { char *prefixin = calloc(LIMIT, sizeof(char)); char *postout = calloc(LIMIT, sizeof(char)); char *infout = calloc(LIMIT, sizeof(char)); char arguments[] = "echo '"; char bc[] = "' | bc "; node_T start_of_tree; start_of_tree = malloc(sizeof(struct expression_tree_node)); if (prefixin == NULL || postout == NULL || infout == NULL || start_of_tree == NULL) { fprintf(stderr, "Unable to malloc.\n"); return EXIT_FAILURE; } int i, ret, count; count = 2; if (argc == 1) { if (isatty(fileno(stdin))) { printf("Please enter your expression: "); } fgets(prefixin, LIMIT, stdin); } else { for (i = 1; i < argc; i++) { strcat(prefixin, argv[i]); strcat(prefixin, " "); } } ret = sscanf(prefixin, "%d", &start_of_tree->top.top); if (ret == 1) { printf("Postfix: %d\n", start_of_tree->top.top); printf("Infix: (%d)\n", start_of_tree->top.top); printf("Result: %d\n", start_of_tree->top.top); return EXIT_SUCCESS; } else { ret = sscanf(prefixin, "%s", start_of_tree->top.topop); if (ret == 0) { fprintf(stderr, "Invalid expression!\n"); return EXIT_FAILURE; } } convert(prefixin + count, postout, infout, start_of_tree); printf("Postfix: %s\n", postout); printf("Infix: %s\n", infout); printf("Result: "); fflush(stdout); strcat(arguments, infout); strcat(arguments, bc); system(arguments); return EXIT_SUCCESS; }