Assignment

A prefix expression is one where each operator appears before its two operands. For example the fully parenthesized infix expression ( ( ( a + b) / (c+d) ) * (e / f) ) becomes the prefix expression * / + a b + c d / e f. The object of this assignment is to write a program to convert a fully parenthesized infix expression to its equivalent prefix expression. Assume the input infix expressions consist only of variables a through z, operators +, -, *, / and parentheses '(', ')' . Use the following algorithm:

(1) Create three stacks of characters: stk1, stk2, stk3.

(2) Read the input infix expression one character at a time and push every character read ( other than ')' ) onto stk1. Do not push the character read if it is ')'.

(3) As long as stk1 is not empty, do the following:

Fetch the top character ( call it c ) of stk1 and pop stk1.

if c is an alphabetic character (a-z), push it onto stk3. (You can use the function islower(c) to test if character is one of a-z.)

if c is an operator, push it onto stk2.

if c is '(' then fetch the top character of stk2, push it onto stk3, and pop stk2.

(4) Print stk3 top to bottom by repeatedly fetching the top of stk3, printing it, and popping stk3, until stk3 is empty.

There is starter code in folder Hwk3 in your course folder on comsci. Open the project file Hwk3.cbp in codeblocks and complete the program hw3.cpp in that project.

The program uses the class template stack from the standard C++ library. Check the examples on the slides for how to push, pop, and check for empty stack.

Attachment:- Tepmlate.rar