Member Avatar for Member #454440

Objective:

Write a C program that will accept an infix expression from the user, build an expression tree using the algorithm described in class and then traverse the tree recursively three times to produce the prefix, infix and postfix expressions. Notice that the infix expression produced from the tree should contain only necessary parentheses.

Specification:

Operands will be represented by single uppercase letters (A..Z). Operators will include (+, -, *, /, %).

Spaces may be included anywhere in the infix expression. They should not be included in result expressions.

You may assume that the input expression will not exceed 80 characters.

The operands should appear in the same order in the output as the input.

The program should error test for the following conditions: An illegal character or unmatched parentheses.

(Note: legal characters are operands, operators and spaces.)

Algorithm:

This is a rather complex program that uses a number of data structures. For example, you might choose to use a queue, two stacks and a series of trees. It will be critical for you to make decisions as to how you are going to implement your data structures. Once you begin generating code it will be difficult and time consuming to change data structures.

You may organize your code as you desire. For example, you might choose to include the entire program in a single (.c) file or you might choose to include several (.c) and several (.h) files.

Sample Runs:

Please enter an Infix expression -- A + (B - C * D) / E

PREFIX : +A/-B*CDE

INFIX : A+(B-C*D)/E

POSTFIX : ABCD*-E/+

Please enter an Infix expression -- A + ( B - C

Unmatched left parenthesis.

  • 2 Contributors
  • 1 Reply
  • 116 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by ddanbe

Dani AI

Generated

As suggested, the most practical references are the Wikipedia pages for an expression tree and the shunting‑yard algorithm. A reliable approach is to build the tree while you parse infix input (use the shunting‑yard idea) and then do three recursive traversals: preorder (prefix), inorder (infix with minimal parentheses), and postorder (postfix).

Use two stacks: one for operators (chars) and one for operand nodes (Node *). While scanning tokens (skip spaces), push operand nodes; push '(' onto ops; on operator, pop and build nodes while top-of-ops has an operator of higher-or-equal precedence; on ')', pop until '(' (error if none). At the end pop remaining operators (error if any '(' remain). Always check for illegal characters and for insufficient operands when popping an operator.

A compact node and precedence helper:

typedef struct Node {
  char c;               /* operator or operand */
  struct Node *left,*right;
} Node;

int prec(char op) {
  if (op=='+'||op=='-') return 1;
  if (op=='*'||op=='/'||op=='%') return 2;
  return 0;
}

To print infix with only necessary parentheses, add parentheses around a child subexpression when its top operator has lower precedence than the parent. Also parenthesize the right child when precedence is equal and the parent operator is non‑associative on the right (for example -, /, %). Preorder and postorder simply visit root-left-right and left-right-root.

Troubleshooting tips: test edge cases like A-B-C, A-(B-C), A/(B*C), and A/(B/C) to verify parentheses rules. Report specific errors (illegal character, unmatched right/left parenthesis, insufficient operands). Instrument the stacks during early testing and remember to free nodes to avoid leaks.

Member Avatar for ddanbe

Start reading!
e.g. Wikipedia.
Search for PREFIX,INFIX and POSTFIX.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.