CISC2200: Data Structure expression evaluation and conversion assignment

1. Overview and Resource

In this lab, we practice writing recursive functions to process algebraic expressions, and using stack in some of the functions. The following are useful resource:

Note from class, and infix, postfix and prefix expression
C library functions to test char type, e.g., isdigit(ch) will return true if ch is a digit charactor (0 through 9). You can also use the following simple statement to convert a digit charactor to the corresponding int value:
```
char ch='5';

int valueofCh=ch-'0';   //this takes advantage of the fact that
		//the ASCII value of '0','1',...'9' are contiguous 
```

C++ string class . Below are a short example demonstrating the usage:

#include 
#include 
using namespace std;

int main()
{
   string greeting="hello world!";

   //string is a class, storing a list of char... 
   //length() member function returns the length of the string.
   //You can use [] operator to access each char ... 
   cout <<greeting.length();
   for (int i=0;i<greeting.length(); i++)
    cout <<greeting[i];

   //You can obtain a substring using substr() function, passing the 
   //index of the first char, and the length of the substr to extract ... 
   string hello=greeting.substr(0,5); //extract a substr of length 5, starting 
		//from the first char of the greeting string object. 
   cout <<hello<<endl;	//this will display hello

   //if you want to convert the string object to C-string (char array)
   //This is useful for a lot of C library and system calls expect such
   //C string 
   const char * cstr = greating.c_str() ; 
   
}

stack (Note that you can write your own stack class for extra credits. As this lab uses stack to store int values and char values, you will need to create a class template if you choose to implement your own stack class.)

2. Requirements:

Evaluate postfix expression: implement the function evaluatePostfix based upon the algorithm given in the code (and discussed in class). Note please refer to the link provided above for string class to find out how to access each char in the string object(Hint: member function length and index operator (i.e., []).)

/* postFix is a stirng that stores a postfix experssion, such as 432+* */
int evaluatePostfix (string postFix)
{
	/* algorithm: 
         Declare a stack of int to store the operands, and the value of the subexpression. 
 	 scan the expression from left to right, char by char 
	 i) if the char is a digit, push the digit's value into the stack
	 ii) if the char is an operand, pop two elements from the stack
              and apply the operation on the two elements, 
              push the result onto the stack 
         when reaching the end of the expression, the value in the stack is the result */ 
}

Note that you should assume that operands are single-digit numbers, so that in postfix expression 34+, 3 and 4 are being added up.

Implement function InfixToPostfix that converts an infix expression to its postfix expression, based upon the following pesudocode.

/* convert an expression from infix format to postfix format */
/* param infix: the expression's infix format, e.g., a+b*c 
   return: the "infix" expression's postfix format, e.g., abc*+ */
string InfixToPostfix (string infix)
{
	// Empty character stack and blank postfix string.
	stack opStack;
	string postFixString = "";


	// Loop through the array (one character at a time) until we reach the end of the string.
        for (int i=0;i<infix.length();i++) 
	{
		if (the i-th char of infix string is a digit or a letter 
		{ 
			//  simply append it to our postfix string.
			postFixString += *cPtr; 
		}
		else if the i-th char of infix is an operator (i.e., '+', '-', '*', '/') 
 			// pop operators off our stack until it is empty, 
			// or, an open parenthesis or an operator with less than or equal precedence is reached 
			while (!opStack.empty() and opStack.top() != '(' and
				the operator on the top of opStack is of equal oe less precedence than current op) 
				postFixString += opStack.top(); // append the top operator from stack 
				opStack.pop();
			}

			// push current operator to the opStack 
		}
		else if i-th char of infix is '('
		{ 
			Push open parenthesis onto our stack
		}
		else if i-th char of infix is ')'
			// When we reach a closing one, start popping off operators until we run into the opening parenthesis.
			while (!opStack.empty()) {
				if (opStack.top() == '(') 
				{ opStack.pop(); 
				  break;
				}
				append the top operator in opStack to postFixString 
				pop top element from opStack 
			}
		}

	}

	 After the input expression has been ran through, if there is any remaining operators left on the stack
	 pop them off and put them onto the postfix string.


	return postFixString;
}

Based upon the pseudocode below (taken from book Data Abstraction & Problem Solving with C++, Carrano & Henry), implement function IsPrefix. Note that the EndOfPrefix function is the helper function to be called by IsPrefix. If you need to obtain a substring of a given string, refer to the resource part of this page.

/* Return the ending index for the prefix expressin start from index "first"  */
/*  return -1 if it fails, e.g., if expr="+",first=0
                                 if expr="+a", first=0 
				 if expr="a*b", first=1 */ 
/* Example: 
 *  expr: +ab, first: 0, return 2, as "+ab" is a prefix ("+", "+a" are not...)
 *  expr: +ab, first: 1, return 1; as "a" is a prefix ("ab" is not)...
 *  expr: +a*cd, first: 0, return 4, as "+a*cd" is a prefix expression ("+a", "+a*c"... are not) 
 *  expr: +a*cd, first 2, return 4, as ... 
 *  expr: *+ab-cd, first 1, return 3, as "+ab" is a prefix expression (not "+ab-",,...) 
 *  expr: *+ab-cd, first 0, return 6, ... */
int EndOfPrefix (string expr, int first)
{
    //pseudocode: 
    last = expr.length()-1;

    //base case 1 
    if (first& or first < last) 
	return -1;  

    //base case 2
    ch = character at position "first" of expr 
    if (ch is a digit or a letter)
	return first        
    else if (ch is an operator)
    {  // so expr should be a string such as "+E1E2", "-E1E2", ... 
       // where E1, E2 are prefix expressions

	//find the end of the first prefix expression 
	firstEnd = EndOfPrefix (expr, first+1) 

        if (firstEnd > -1) // if we find the end of E1 
	    //E2's end will be the end of current expression
            return EndOfPrefix (expr, firstEnd+1)
        else
           return -1 

    } else 
       return -1; 
   
}


//Return true if the expr is a valid prefix expression; else return false
bool IsPrefix (string expr)
{
   //pseudocode:
   int End = EndofPrefix (expr,0);

   // if the end of prefix expression is the last character of the string, then the expr is a prefix 
   if (End&0 and End==expr.length()-1)
	return true;
   else 
	return false; 
}

Implement the function PrefixToPostfix. Hint: try to solve this problem recursively.

/* return a postfix expression for the given expression in prefix */
string PrefixToPostfix (string prefix)
{

}

Implement the following function recursively.

/* return the integer value of the prefix expression */
/* precondition: prefix does not contain any letter, 
   
int evaluatePrefix(string prefix)
{

}

Submission

Please submit each source files, class specficiation file (header file) and implemenetation file (.cpp file), and driver program using the script given. For example,

submit2200 FINALLAB finallab.cpp
...