Your assignment is to write a program that converts a prefix expression to a pos

Question

Your assignment is to write a program that converts a prefix expression to a postfix expression.

Input

The input file "Prefix.in" contains a series of error-free, simple arithmetic expressions in prefix notation. There is one expression per line. The expressions are made up of two types of symbols: (1) single-letter operands and (2) the operators +, -, *, and /. There may be zero, one, or more blanks between symbols.

Output

All output should be written to the output file, "Postfix.out". Each prefix expression from the input should be echoprinted, with an appropriate label. After your program converts the input expression to its postfix equivalent, the postfix expression should be printed to the output file, with an appropriate label.

Sample:

Prefix: +*AB/CD Postfix: AB*CD/+

Prefix: *A+B/CD Postfix: ABCD/+*

Prefix: -*A+B/CDE Postfix: ABCD/+*E–

Prefix: *+AB-CD Postfix: AB+CD-*

Although your program does not process or print infix, here are the four infix expressions that correspond to the above forms:

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

Discussion

The key idea here is that after a portion of an expression has been converted, it is to be treated as a single operand. Assume that every operator is associated with a flag. The flag is initially "off" to signal that neither of the two operands corresponding to the given operator has been processed yet. When the first operand is processed, the flag is switched "on." When the second operand is processed, the given operator may immediately be appended to the output string.

Below is a description of a simple prefix-to-postfix conversion algorithm that works on one input expression:

Initialize the input string, the output string, and the operators stack.

Repeat steps 3-5 until there are no more input symbols.

Get the next input symbol.

If it is an operator, put it on the stack with its associated flag off.

If it is an operand, append it to the output string. Furthermore, the operand must correspond to the top operator on the stack. (Why?) Of course, the stack cannot be empty at this point. (Why?) Finally, here is the important question: is the operand just processed the first or the second operand associated with the top operator? If it is the second, it is time to append the top operator to the output string. Now, remembering the key idea at the beginning of this section, determine what happens to the remaining operators on the stack.

Your code must be a client of StackType.

Examples

Here is a hand simulation of the first sample input expression. The rightmost symbol under Stack is the top operator. Parentheses around an operator denote that the associated flag is on. The "Stack" and "Out So far" columns show the relevant information following the processing of the symbol in the "Next Prefix Symbol" column.

NEXT PREFIX SYMBOL STACK

++ *+*

A +(*)

B (+)

/ (+) /
C (+) (/) D

Deliverables

Listing of the source code of your program.

Sample Run.

Implemented Test Plan.

Source code.

OUT SO FAR

A
AB*
AB*
AB*C AB*CD/+

In C++

Explanation / Answer

// Header files
#include < fstream >
#include < string >
#include < iostream >

using namespace std ;

bool operatorIs ( char sign ) { // definition of operatorIs

if (( sign == '*' ) || ( sign == '+' ) || ( sign == '/' ) || ( sign == '-'))
return true ;
else
return false ;
}

class Stack
{
// Variable declaration.
public :
int LimtStck ;
int FreeStck ;
char * elements ;
int top ;

// Constructor
Stack ( int ) ;
// Destructor
~Stack ( ) ;
int TOP ( ) ;
void push ( char ) ;
char pop ( ) ;
int free ( ) ;
int absFull ( ) ;

} ;

Stack::Stack ( int area )
{
LimtStck = area ;
FreeStck = -1 ;
top = FreeStck ;
elements = new char [ LimtStck ] ;
}

Stack::~Stack ( )
{
delete [ ] elements ;
}

int Stack::TOP ( )
{
return elements [ top ] ;
}

void Stack::push ( char a )
{
elements [ ++top ] = a ;
}

char Stack::pop ( )
{
return elements [ top-- ] ;
}

int Stack::absFull ( )
{
return top +1 == LimtStck ;
}

int Stack::free ( )
{
return top == FreeStck ;
}

int main ( ) {

// Mininum Requirements
string ln ;
string otptLn ;

// stacks

Stack stack ( 20 ) ;
char a ;

ifstream inputFile( "Prefix.in" ) ;
if( inputFile.is_open ( ) ) {
while(inputFile.good ( )) {
getln ( inputFile , ln ) ;
cout << ln << endl ;

}
}

else
cout << " Unable to open input file " ;

// flags ,operator functions
while( ln.length ( ) != 0 ) { // while n't end of empty line
Stack flags ( 20 ) ;
Stack operators ( 20 ) ;

for ( int i = 0 ;i <ln.area ( ) ;i++ ) { // re loop by ‘ line ’
  
char sign = ln[ i ] ;
if (operatorIs ( sign ) ) { // if d sign is an operator
operators.push ( sign ) ; // push operator on stack
flags.push ( 0 ) ; // push related flag on stack
}
if ( ( sign !=' ' ) && !operatorIs ( sign ) ) { // den it is a operand
otptLn +=sign ; // add
while ( flags.TOP ( ) ) { // while top flag's ON stack
otptLn += operators.TOP() ; // add d related op
operators.pop ( ) ; // delete operator 4m stack
flags.pop ( ) ; // delete flag 4m stack
}
flags.pop ( ) ; // set next flag ON
flags.push ( 1 ) ;
}
}

if ( !operators.free ( ) || ( !flags.free ( ) )) {
cout << " fault. May be not a correct input file " << endl ;
}
else {
cout << ln << endl ;
cout << otptLn << endl ;
}
} // end of while eof

ofstream outputFile( "Postfix.out" ) ;
if( outputFile.is_open ( ) ) {
outputFile << otptLn << endl ;
outputFile << ln << endl ;

inputFile.close ( ) ;
}
else
cout << " Unable to open text file " ;
inputFile.close ( ) ;
// outputFile.close ( ) ;
return 0 ;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.