Implement the function evaluatePostfix based upon the algorithm given in the cod
ID: 3694522 • Letter: I
Question
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 stringclass to find out how to access each char in the string object(Hint: member function length and index operator (i.e., []).)
Note that you should assume that operands are single-digit numbers, so that in postfix expression 34+, 3 and 4 are being added up. For extra credit, you can support operands that are two or more digits long. To do so, you need to:
Modify InfixToPostfix so that between the two operands you use space to separate them: e.g., for 34+12, the function return 34 12+
In evaluatePostfix function, in step i), you need to use a loop to read digits until reaches space or operator, and meanwhile find out the values of the operands...
Based upon the pseudocode in the handout (page 167, 169), implement the function IsPrefix. Note that the EndOfPrefix function is the helper function to be called byIsPrefix. If you need to obtain a substring of a given string, refer to the resource part of this page.
Based upon the pseudocode in the handout (page 171), implement the function PrefixToPostfix.
Extra Credit: based upon the pseudocode in the handout (page 170), implement the following function, and test it.
____________________________________________________________________________________________________________
#include <iostream>
#include <stack>
#include <string>
#include <ctype.h>
using namespace std;
// Simply determine if character is one of the four standard operators.
bool isOperator(char character) {
if (character == '+' || character == '-' || character == '*' || character == '/') {
return true;
}
return false;
}
// If the character is not an operator or a parenthesis, then it is assumed to be an operand.
bool isOperand(char character) {
if (!isOperator(character) && character != '(' && character != ')') {
return true;
}
return false;
}
// Compare operator precedence of main operators.
// Return 0 if equal, -1 if op2 is less than op1, and 1 if op2 is greater than op1.
int compareOperators(char op1, char op2) {
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) { return -1; }
else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) { return 1; }
return 0;
}
string InfixToPostfix (string infix)
{
// Empty character stack and blank postfix string.
stack<char> opStack;
string postFixString = "";
// Get a pointer to our character array.
const char *cPtr = infix.c_str();
// Loop through the array (one character at a time) until we reach the end of the string.
while (*cPtr != '') {
if (isOperand(*cPtr))
{
// If operand, simply add it to our postfix string.
postFixString += *cPtr;
}
else if (isOperator(*cPtr)) {
// If it is an operator, pop operators off our stack until it is empty,
// an open parenthesis or an operator with less than or equal precedence.
while (!opStack.empty() && opStack.top() != '(' &&
compareOperators(opStack.top(),*cPtr) <= 0) {
postFixString += opStack.top();
opStack.pop();
}
opStack.push(*cPtr);
}
else if (*cPtr == '(')
{
// Simply push all open parenthesis onto our stack
opStack.push(*cPtr);
}
else if (*cPtr == ')') {
// 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; }
postFixString += opStack.top();
opStack.pop();
}
}
// Advance our pointer to next character in string.
cPtr++;
}
// 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.
while (!opStack.empty()) {
postFixString += opStack.top();
opStack.pop();
}
// Show the postfix string at the end.
//cout << "Postfix is: " << postFixString << endl;
return postFixString;
}
/* return true if the expr string does not contain variables */
bool NoVariable (string postFix)
{
int length=postFix.length();
for (int i=0;i<length;i++)
if (!isdigit(postFix[i]) && !isOperator(postFix[i])) {
return false;
}
return true;
}
int evaluatePostfix (string postFix)
{
/* algorithm:
Declare a stack of int to store the operands, and also the result 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 */
}
/* Return the ending index for the prefix expressin start from start */
/* Example:
* expr: +ab, start: 0, return 2, as "+ab" is a prefix ("+", "+a" are not...)
* expr: +ab, start: 1, return 1; as "a" is a prefix ("ab" is not)...
* expr: +a*cd, start: 0, return 4, as "+a*cd" is a prefix expression ("+a", "+a*c"... are not)
* expr: +a*cd, start 2, return 4, as ...
* expr: *+ab-cd, start 1, return 3, as "+ab" is a prefix expression (not "+ab-",,...)
* expr: *+ab-cd, start 0, return 6, ... */
int EndOfPrefix (string expr, int start)
{
//Todo by you... --referred to handout ...
}
//Return true if the expr is a valid prefix expression; else return false
bool IsPrefix (string expr)
{
//Todo by you --
}
/* return a postfix expression for the given expression in prefix */
string PrefixToPostfix (string prefix)
{
}
int main()
{
char cont;
string expr;
string postFix;
do {
cout <<"Enter an infix or prefix expression:";
cin >> expr;
/* uncomment this after you implement the two functions to test and convert prefix...
if (IsPrefix (expr)) {
//Todo: call prefix to postfix conversion function
PrefixToPostfix (expr);
} else {
*/
//For now:: assume is infix
postFix = InfixToPostfix (expr);
// }
cout <<"Postfix is: " << postFix << endl;
if (!NoVariable(postFix)){
cout << "Value is " << evaluatePostfix(postFix)<<endl;
}
cout <<"Try again:(Y/N):";
cin >> cont;
} while (cont=='y' || cont=='Y');
}
Explanation / Answer
#include <iostream>
#include <stack>
#include <string>
#include <ctype.h>
using namespace std;
// Simply determine if character is one of the four standard operators.
bool isOperator(char character) {
if (character == '+' || character == '-' || character == '*' || character == '/') {
return true;
}
return false;
}
// If the character is not an operator or a parenthesis, then it is assumed to be an operand.
bool isOperand(char character) {
if (!isOperator(character) && character != '(' && character != ')') {
return true;
}
return false;
}
// Compare operator precedence of main operators.
// Return 0 if equal, -1 if op2 is less than op1, and 1 if op2 is greater than op1.
int compareOperators(char op1, char op2) {
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) { return -1; }
else if ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/')) { return 1; }
return 0;
}
string InfixToPostfix (string infix)
{
// Empty character stack and blank postfix string.
stack<char> opStack;
string postFixString = "";
// Get a pointer to our character array.
const char *cPtr = infix.c_str();
// Loop through the array (one character at a time) until we reach the end of the string.
while (*cPtr != '') {
if (isOperand(*cPtr))
{
// If operand, simply add it to our postfix string.
postFixString += *cPtr;
}
else if (isOperator(*cPtr)) {
// If it is an operator, pop operators off our stack until it is empty,
// an open parenthesis or an operator with less than or equal precedence.
while (!opStack.empty() && opStack.top() != '(' &&
compareOperators(opStack.top(),*cPtr) <= 0) {
postFixString += opStack.top();
opStack.pop();
}
opStack.push(*cPtr);
}
else if (*cPtr == '(')
{
// Simply push all open parenthesis onto our stack
opStack.push(*cPtr);
}
else if (*cPtr == ')') {
// 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; }
postFixString += opStack.top();
opStack.pop();
}
}
// Advance our pointer to next character in string.
cPtr++;
}
// 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.
while (!opStack.empty()) {
postFixString += opStack.top();
opStack.pop();
}
// Show the postfix string at the end.
//cout << "Postfix is: " << postFixString << endl;
return postFixString;
}
/* return true if the expr string does not contain variables */
bool NoVariable (string postFix)
{
int length=postFix.length();
for (int i=0;i<length;i++)
if (!isdigit(postFix[i]) && !isOperator(postFix[i])) {
return false;
}
return true;
}
int evaluatePostfix (string postFix)
{
/* algorithm:
Declare a stack of int to store the operands, and also the result 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 */
stack<int> myStack;
for(int i = 0; i < postFix.size(); i++){
if(postFix[i] >= '0' && postFix[i] <= '9') myStack.push(postFix[i] - '0');
else{
char opt = postFix[i];
int op1 = myStack.top();
myStack.pop();
int op2 = myStack.top();
myStack.pop();
switch(opt){
case '+':
myStack.push(op1 + op2);
break;
case '-':
myStack.push(op1 - op2);
break;
case '*':
myStack.push(op1 * op2);
break;
case '/':
myStack.push(op1 / op2);
break;
case '%':
myStack.push(op1 % op2);
break;
}
}
}
return myStack.top();
}
/* Return the ending index for the prefix expressin start from start */
/* Example:
* expr: +ab, start: 0, return 2, as "+ab" is a prefix ("+", "+a" are not...)
* expr: +ab, start: 1, return 1; as "a" is a prefix ("ab" is not)...
* expr: +a*cd, start: 0, return 4, as "+a*cd" is a prefix expression ("+a", "+a*c"... are not)
* expr: +a*cd, start 2, return 4, as ...
* expr: *+ab-cd, start 1, return 3, as "+ab" is a prefix expression (not "+ab-",,...)
* expr: *+ab-cd, start 0, return 6, ... */
int EndOfPrefix (string expr, int start)
{
//Todo by you... --referred to handout ...
}
//Return true if the expr is a valid prefix expression; else return false
bool IsPrefix (string expr)
{
//Todo by you --
}
/* return a postfix expression for the given expression in prefix */
string PrefixToPostfix (string prefix)
{
}
int main()
{
char cont;
string expr;
string postFix;
do {
cout <<"Enter an infix or prefix expression:";
cin >> expr;
/* uncomment this after you implement the two functions to test and convert prefix...
if (IsPrefix (expr)) {
//Todo: call prefix to postfix conversion function
PrefixToPostfix (expr);
} else {
*/
//For now:: assume is infix
postFix = InfixToPostfix (expr);
// }
cout <<"Postfix is: " << postFix << endl;
if (!NoVariable(postFix)){
cout << "Value is " << evaluatePostfix(postFix)<<endl;
}
cout <<"Try again:(Y/N):";
cin >> cont;
} while (cont=='y' || cont=='Y');
}