C++11 Prefix Expression Evaluation Program Develop a program with functions that

Question

C++11 Prefix Expression Evaluation Program

Develop a program with functions that 1.) determine whether an expression is a valid prefix expression, and 2.) evaluate the expression if it is in fact a valid prefix expression.
For reference, check this article on prefix expressions:
https://en.wikipedia.org/wiki/Polish_notation
Prefix Example:
(5-6)x7 in prefix is x-567.

Psuedocode for a recursive valued function endPre, which examines the expression that begins at position first of the string strExp and to locate the end of the first prefix expression it finds. If successful, the function returns the index of the end of the prefix expression. If no such prefix expression exists, endPre returns –1. Use the following psuedocode to implement endPre:
// Precondition: The substring of strExp from the index First through the end of the string contains no blank characters.
// Postcondition: Returns the index of the last character in the prefix expression that begins at index First of strExp, or —1 if no such prefix expression exists.
endPre(strExp: string, First: integer): integer
last = strExp. 1ength() - 1
if (First < 0 or First > last)
   return -1
ch = character at position First of strExp
if (ch is an identifier)
   return First
// Index of last character in simple prefix expression
else if (ch is an operator)
{
// Find the end of the first prefix expression
firstEnd = endPre(strExp, fi rst + 1)
// If the end of thefint prefix expression was found, find the end of the second prefix expression
if (fi rstEnd > -1) return endPre(strExp, fi rstEnd + 1) // Point Y
else
   return -1
}
else
   return -1
You can use the function endPre to determine whether a string contains a prefix expression as follows:
isPrefix(strExp:string):boolean
   lastChar=endPre(strExp,0)
   return (lastChar>=0) and (lastChar==strExp.length()-1)

Use the following psuedocode to develop a function evaluatePrefix which evaluates a valid prefix expression:
//Precondition: strExp is a string containing a valid prefix expression with no blanks
evaluatePrefix(strExp: string): float
strLength = the length of strExp
if (strLength == 1)
   return value of the identifier
else {
op = strExp[0]
// Find the end of the first prefix expression—will be the first operand
endFirst = endPre(strExp, 1)
// Recursively evaluate this first prefix expression
operand1 = evaluatePrefix(strExp[1..endFirst]);
// Recursively, evaluate the second prefix expression-will be the second operand
endSecond = strLength - endFirst + 1
operand2 = evaluatePrefix(strExp[endFirst + 1, endSecond])
// Evaluate the prefix expression
return operand1 op operand2
}

Use the functions to check if various strings are valid prefix expressions, and evaluate the expressions: +*ab-cd and *ab+-cd, where a = 2, b = 5, c = 3, and d = 7.

Explanation / Answer

#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;
struct node
{
int data;
node *next;
}*p = NULL, *top = NULL, *save = NULL, *ptr;
void push(int x)
{
p = new node;
p->data = x;
p->next = NULL;
if (top == NULL)
{
top = p;
}
else
{
save = top;
top = p;
p->next = save;
}
}
char pop()
{
if (top == NULL)
{
cout<<"underflow!!";
}
else
{
ptr = top;
top = top->next;
return(ptr->data);
delete ptr;
}
}
int main()
{
char x[30];
int a, b;
cout<<"enter the balanced expression ";
cin>>x;
for (int i = 0; i < strlen(x); i++)
{
if (x[i] >= 48 && x[i] <= 57)
push(x[i]-'0');
else if (x[i] >= 42 && x[i] <= 47)
{
a=pop();
b=pop();
switch(x[i])
{
case '+':
push(a+b);
break;
case '-':
push(a-b);
break;
case '*':
push(a*b);
break;
case '/':
push(a/b);
break;
}
}
}
cout<<"ans is "<<pop()<<endl;
getch();
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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