[Solved] CS2123 Data Structures Assignment 2: Stacks

Evaluate Postfix (10 points)

Sketch of algorithm for evaluating postfix strings:

• Create stack s.
• For each token, x, in the postfix expression: 1 If x is T or F push it into the stack s.
  • Else if x is a unary operator i pop an operand, op1, from s
    • compute x op1 (see unary table below)
    • push the result into s
  • Else if x is a binary operator i pop an operand, op2, from s ii pop an operand, op1, from s

iii compute op1 op2 x iv push the result into s

• If you do not have enough operands in s to perform an operation you should return an error in the boolean.
• Likewise, if s contains more than one operand after all of the tokens are evaluated you should return an error in the boolean.
• Otherwise pop and return the only value in s.

Unary operations:

Binary operations:

Convert Infix to Postfix (10 points)

Sketch of algorithm for converting postfix strings to infix strings:

• Create stack s.
• For each token, x, in the postfix expression: 1 If x is T or F push it into the stack s.
  • Else if x is a unary operator i pop an operand, op1, from s
    • push the string (op1 x) into s
  • Else if x is a binary operator i pop an operand, op2, from s ii pop an operand, op1, from s
    • push the string (op1 x op2) into s
  • You assume that the postfix string is well formatted (feel free to implement error checking if you would like).
  • pop and return the value in s.

Hints for memory management:

• Every string that you push into your stack should be malloc-ed.
• You should free strings after popping them (be sure to use them before freeing them).
• Operator tokens will be freed after usage since they are not put into the stack.

Deliverables:

Your solution should be submitted as booleanEvaluation.c,

booleanEvaluation.h, and makefile. Also attach any additional files you create to solve this problem.

Upload these file to Blackboard under Assignment 2. Do not zip your files.

To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks.