I am having some trouble with this C++ program. I wrote the codes, ran it and my
ID: 3599265 • Letter: I
Question
I am having some trouble with this C++ program. I wrote the codes, ran it and my infix and postfix doesn't seem to be working. I just can't figure out what and why this is happening. If I could be helped, I'd really appreciate it. I have attached my codes and the program description below.
C++ program description
You are going to exercise your knowledge of stacks.
First, look up and familiarize yourself with the STL stack class. You will use this class for this
assignment.
1 - Infix to Postfix
Implement the Infix to Postfix algorithm discussed in class:
string infixToPostfix(string exp)
This will take an infix expression as an argument, and return the corresponding postfix expression.
Operands will be single upper-case letter, and operators will be *, / +, -. You may assume the input
expression is correct. Your algorithm should skip over any blank spaces it finds.
2 - Postfix Evaluation
Implement the Postfix Evaluation algorithm discussed in class.
double evaluatePostfix(string exp)
This will take a postfix expression of the form generated in part 1, and evaluate it as a double value.
See below for the values of the operands.
3 - PostfixToPrefix
You will implement an algorithm to convert from postfix to prefix.
string postfixToPrefix(string exp)
The postfix to prefix conversion algorithm is as follows:
Create a stacks, S, of strings
Scan the postfix expression from left to right
(skip over whitespace)
If the character (ch) is an operand:
S.push(ch)
If the character (ch) is an operator,
x = s.pop();
y = s.pop();
S.push(ch + y + x) (string concatenation)
At the end, the resulting prefix string will be the only element in the
stack.
Main Program
Repeatedly:
1. Read an infix expression from a file (a single line), consisting of upper case letters and
operators +, -, *, /, and possible blank spaces. Assume the expression is correct.
2. Invoke the infixToPostfix function to create the corresponding postfix expression.
3. Invoke the postfixToPrefix function, passing the postfix expression generated in step 2, to
create the corresponding prefix expression.
4. Invoke the evaluatePostfix function, passing the postfix expression generated in step 2, to
evaluate the expression. Assume the following operand values (this may be hard-coded):
A: 2.0 B: 3.0 C: 4.0 D: 5.0 E: 6.0
Use the following file of infix expressions for your run:
***NOTE: This file should be opened as a .txt file.***
A + B * C
( A + B ) * C
A *( B + C * D )+ E
A * ( ( E / B ) + C )
( A – B ) / C * ( D + E )
Output should look like this:
*****************************************
LinkedStack.cpp Code:
*****************************************
#include // For assert
#include "LinkedStack.h" // Header file
#include
#include
#include
LinkedStack::LinkedStack() : topPtr(nullptr)
{
} // end default constructor
LinkedStack::LinkedStack(const LinkedStack& aStack)//deep copy
{
// Point to nodes in original chain
Node* origChainPtr = aStack.topPtr;
if (origChainPtr == nullptr)
topPtr = nullptr; // Original stack is empty
else
{
// Copy first node and get the item
topPtr = new Node();
topPtr->setItem(origChainPtr->getItem());
// Point to first node in new chain
Node* newChainPtr = topPtr;
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
// Copy remaining nodes
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node* newNodePtr = new Node(nextItem);
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer unless gets to nullptr
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(nullptr); // Flag end of chain
} // end if
} // end copy constructor
LinkedStack::~LinkedStack()
{
// Pop until stack is empty
while (!isEmpty())
pop();
} // end destructor
bool LinkedStack::push(const ItemType& newItem)
{
Node* newNodePtr = new Node(newItem, topPtr);
topPtr = newNodePtr;
newNodePtr = nullptr;
return true;
} // end push
bool LinkedStack::pop()
{
bool result = false;
if (!isEmpty())
{
// Stack is not empty; delete top
Node* nodeToDeletePtr = topPtr;
topPtr = topPtr->getNext();
// Return deleted node to system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
result = true;
} // end if
return result;
} // end pop
ItemType LinkedStack::peek() const
{
assert(!isEmpty()); // Enforce precondition during debugging
// Stack is not empty; return top
return topPtr->getItem();
} // end getTop
bool LinkedStack::isEmpty() const
{
return topPtr == nullptr;
} // end isEmpty
bool LinkedStack::operand(char c) {
if (c >= '0' && c <= '9') {
return true;
}
if (c >= 'A' && c <= 'Z') {
return true;
}
if (c >= 'a' && c <= 'z') {
return true;
}
if (c >= '0' && c <= '9') {
return true;
}
return false;
}
bool LinkedStack::rightParent(char c) {
if (c == ')')
{
return true;
}
return false;
}
bool LinkedStack::leftParent(char c) {
if (c == '(')
{
return true;
}
return false;
}
bool LinkedStack::isOperator(char c) {
if (c == '+' || c == '*' || c == '-' || c == '/' )
return true;
return false;
}
bool LinkedStack::check(char c) {
if(!operand(c) || !isOperator(c) || !rightParent(c) || !leftParent(c) || !isupper(c))
{
return false;
}
return true;
}
bool LinkedStack::highOperator(char x, char y) {
int op1 = opLevel(x);
int op2 = opLevel(y);
if (op1 == op2)
{
return true;
}
return op1 > op2 ? true : false;
}
int LinkedStack::rightAssoc(char c) {
if (c == '^')
{
return true;
}
return false;
}
int LinkedStack::opLevel(char c) {
int lvl;
switch (c)
{
case '+':
lvl = 1;
break;
case'-':
lvl = 1;
break;
case'*':
lvl = 2;
break;
case'/':
lvl = 2;
break;
default:
break;
}
return lvl;
}
string LinkedStack::infixToPostfix(string exp) {
LinkedStack op;//stack obj
string ot; // ="";//output string obj, empty
for (int a = 0; a < exp.length(); a++)
{
//for (auto& c : exp)
char c = exp[a];
//if blank spaces continue
if (check(c))
{continue;
}
//if the token is an operand then push in the string
else if (operand(c))
{
ot+=c;
}
else if (isOperator(c)) // (c == '+' || c == '*' || c == '-' || c == '/')
{
while (!op.isEmpty() && (!leftParent(op.peek()) && highOperator(op.peek(), c)))
{
ot += op.peek();//top elem
op.pop();
}
op.push(c);
}
else if (leftParent(c) ) //if token is '(' push in the stack
{
op.push(c);
}
//check if the top item is ')'
else if (rightParent(c))
{
while (!op.isEmpty() && !leftParent(op.peek()))
{
ot += op.peek();
op.pop();
}
op.pop();
}
}
while (!op.isEmpty())
{
ot +=op.peek();//inserting the remaining elem of stack in output string
op.pop();
}
return ot;
}
string LinkedStack::postfixToPrefix(string exp) {
LinkedStack S;
string px; //empty strings
//string add;
for (int a = 0; a < exp.length(); a++)
{
char c = exp[a];
//check forspaces
if (check(c)) {
continue;
}
//if operand then
if (operand(c))
{
S.push(c);
}
else if (isOperator(c)) {
char a = S.peek();
S.pop();
char b = S.peek();
S.pop();
S.push(c + b + a);
}
}
if(!S.isEmpty())
{
px =S.peek();
S.pop();
}
return px;
}
double LinkedStack::value(char c) {
//double x;
switch (c) {
case'A':
return 2;
break;
case'B':
return 3;
break;
case'C':
return 4;
break;
case'D':
return 5;
break;
case'E':
return 6;
break;
}
}
double LinkedStack::perform(char c, char y, char x) {
double res;
switch (c) {
case '+':
res = value(y) + value(x);
break;
case '-':
res = value(y) - value(x);
break;
case '*':
res = value(y) * value(x);
break;
case '/':
res = value(y) / value(x);
break;
}
return res;
}
double LinkedStack::evaluatePostfix(string exp) //To get the value
{
LinkedStack S;
double ev;
for (int x = 0; x < exp.length() ; x++)
{
char c = exp[x];
if (operand(c)) {
//value of operand and push it
S.push(c);
}
else if (isOperator(c))
{
//if operator pop twice and calculate the two operands with operator
char x = S.peek();
S.pop();
char y = S.peek();
S.pop();
//while operand, put the values, by using value
double res = perform(c, y, x);
S.push(res);
}
}
ev=S.peek();
//return S.peek();
return ev;
}
***********************************
LinkedStack.h Code:
**********************************
#ifndef LINKED_STACK_
#define LINKED_STACK_
#include "Node.h"
#include
#include
#include
class LinkedStack
{
private:
Node* topPtr; // Pointer to first node in the chain;
// this node contains the stack's top
//char c;
/* stack op;
stackpx;*/
public:
// stack S;
LinkedStack();
LinkedStack(const LinkedStack& aStack); // Copy constructor
~LinkedStack();
bool isEmpty() const;
bool push(const ItemType& newEntry);
bool pop();
ItemType peek() const;
bool LinkedStack::rightParent(char c);
bool LinkedStack::leftParent(char c);
bool check(char c);
bool operand(char c);
bool isOperator(char c);
bool highOperator(char x, char y);
int opLevel(char c);
double value(char c);
// int value(char c);
double perform(char c,char y,char x);
int rightAssoc(char c);
string infixToPostfix(string exp);
string postfixToPrefix(string exp);
double evaluatePostfix(string exp);
};
#endif
**********************************************
LinkedStackTest.cpp Code:
**********************************************
#include "LinkedStack.h"
#include
#include
#include
#include
using namespace std;
int main()
{
LinkedStack con;
string line;
string fileName;
cout << "enter the file name:";
cin >> fileName;
ifstream myFile(fileName);
cout << "infix " << "prefix " << "postfix " << "value ";
cout << " ";
while (getline(myFile, line))
{
string infix = "";
for (int x = 0; x < line.length(); x++)
{
char c = line[x];
if (c == ' ')
{
continue;
} infix += c;
}
cout << infix;
cout<<(line.length() > 15 ? " " : " ") << con.postfixToPrefix(con.infixToPostfix(line));
cout << (con.postfixToPrefix(con.infixToPostfix(line)).length() > 8 ? " " : " ");
cout << con.infixToPostfix(line);
cout << (con.infixToPostfix(line).length() > 7 ? " " : " ");
cout << con.evaluatePostfix(con.infixToPostfix(line)) << ' ';
}
myFile.close();
}
**************************************
Node.cpp Code:
**************************************
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
**************************************
Node.h Code:
**************************************
#ifndef NODE_
#define NODE_
#include
using namespace std;
typedef int ItemType;
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#endif
infiz prefiz postfiz value A+B C A BC ABC+ (A+B) *C ABC +ABC 14.0 20.0 etc...Explanation / Answer
//#include "LinkedStack.h"
//#include "Node.h"
#include<iostream>
#include<fstream>
#include<stack>//only used in post to pre
#include<assert.h>
#include<math.h>
using namespace std;
//----------------------------------------------------------------------
#ifndef NODE_
#define NODE_
typedef int ItemType;
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#endif
#ifndef LINKED_STACK_
#define LINKED_STACK_
class LinkedStack
{
private:
Node* topPtr; // Pointer to first node in the chain;
// this node contains the stack's top
public:
LinkedStack();
LinkedStack(const LinkedStack& aStack); // Copy constructor
~LinkedStack();
bool isEmpty() const;
bool push(const ItemType& newEntry);
bool pop();
ItemType peek() const;
};
#endif
Node::Node() : next(NULL)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(NULL)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
}
LinkedStack::LinkedStack() : topPtr(NULL)
{
} // end default constructor
LinkedStack::LinkedStack(const LinkedStack& aStack)
{
// Point to nodes in original chain
Node* origChainPtr = aStack.topPtr;
if (origChainPtr == NULL)
topPtr = NULL; // Original stack is empty
else
{
// Copy first node
topPtr = new Node();
topPtr->setItem(origChainPtr->getItem());
// Point to first node in new chain
Node* newChainPtr = topPtr;
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
// Copy remaining nodes
while (origChainPtr != NULL)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node* newNodePtr = new Node(nextItem);
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(NULL); // Flag end of chain
} // end if
} // end copy constructor
LinkedStack::~LinkedStack()
{
// Pop until stack is empty
while (!isEmpty())
pop();
} // end destructor
bool LinkedStack::push(const ItemType& newItem)
{
Node* newNodePtr = new Node(newItem, topPtr);
topPtr = newNodePtr;
newNodePtr = NULL;
return true;
} // end push
bool LinkedStack::pop()
{
bool result = false;
if (!isEmpty())
{
// Stack is not empty; delete top
Node* nodeToDeletePtr = topPtr;
topPtr = topPtr->getNext();
// Return deleted node to system
nodeToDeletePtr->setNext(NULL);
delete nodeToDeletePtr;
nodeToDeletePtr = NULL;
result = true;
} // end if
return result;
} // end pop
ItemType LinkedStack::peek() const
{
assert(!isEmpty()); // Enforce precondition during debugging
// Stack is not empty; return top
return topPtr->getItem();
} // end getTop
bool LinkedStack::isEmpty() const
{
return topPtr == NULL;
}
//-----------------------------------------------------------main program is down here-----------------------------------------------------------------------
class Parse
{
public:
int item;
string a,p;
int isoperand(char operand) //checks if character is an operand
{
if ((operand >= 0x0030 && operand <= 0x0039)|| (operand >= 0x0041 && operand <= 0x005A) || (operand >= 0x0061 && operand <= 0x007A)) //hex values (in unicode) for 0-9,a-z,A-Z
return 1;
return 0;
}
int precedence(char operators)
{
int level=0;
switch (operators)
{
case '+':
case '-':
level = 1;
break;
case '*':
case '/':
level = 2;
break;
case '%':
level = 3;
break;
case '^':
level = 4;
break;
}
return level;
}
void entersentinel(string *a) //a sentinel ')' is added to check the ending of the array
{
(*a)[(*a).length()]=')';
}
string infixToPostfix()
{
char p[a.length()];
entersentinel(&a);
LinkedStack s;
int j = 0, k;
char popped;
s.push('(');
for (int i = 0; !s.isEmpty(); i++)
{
if(a[i]==' ')
continue;
if (isoperand(a[i]))
{
p[j] = a[i];
j++;
}
else if (a[i] == '(')
{
s.push(a[i]);
}
else if (k = precedence(a[i])) //checking whether its an operator & if it is then what is it
{
popped = (char)s.peek();
s.pop();
while (popped != '(')
{
if (precedence(popped) >= k)
{
p[j] = popped;
j++;
}
else
{
s.push(popped);
break;
}
popped = (char)s.peek();
s.pop();
}
if(popped=='(')
s.push('(');
s.push(a[i]);
}
else if (a[i] == ')')
{
popped = (char)s.peek();
s.pop();
while (popped != '(')
{
p[j] = popped;
j++;
popped = (char)s.peek();
s.pop();
}
p[j] = '';
}
}
s.~LinkedStack();
return (string)p;
}
string getOutput()
{
return p;
}
int isoperand_no(char operand) //checks if character is an operand
{
if (operand >= 0x0030 && operand <= 0x0039) //hex values (in unicode) for 0-9
return 1;
return 0;
}
double Postfix2Eval(string p)
{
entersentinel(&p);
LinkedStack s;
int flag = 0; //if flag=0 then function gives the ans.
double x, y, ans;
for (int i = 0; p[i] != ')'; i++)
{
int a = isoperand_no(p[i]);
if (a)
{
item = p[i] - '0'; //converting character (like '8') into the int (like 8) [needed to subtract the relative position] [typecasting will return its unicode no.]
s.push(item); //if its a no. push into the stack
}
else if (checkvar(p[i]))
{
cout << "Enter the value for " << p[i] << endl;
cin >> item;
s.push(item);
}
else
{
x = s.peek(); //pop two no. if operator is encountered
s.pop();
y = s.peek();
s.pop();
switch (p[i]) //do the required operation
{
case '+':
ans = y + x;
break;
case '-':
ans = y - x;
break;
case '*':
ans = y*x;
break;
case '/':
ans = y / x;
break;
case '^':
ans = pow(y, x);
break;
// case '%':
// ans = y%x;
// break;
default:
cout << "Sorry, " << p[i] << " is not an operator. ";
flag = 1; //flag=1 to stop
}
if (flag == 1)
break;
item = ans;
s.push(item); //push the ans. to the stack
}
}
if (flag == 0)
{
double ret=s.peek();
return ret;
} //retrun top of the stack as the final ans.
return -1;//if flag==1, there is operator error
}
int checkvar(char operand) //check if there is a variable input
{
if ((operand >= 0x0041 && operand <= 0x005A) || (operand >= 0x0061 && operand <= 0x007A)) //checks bet. a-z and A-Z for variable input
{
return 1;
}
return 0;
}
string Postfix2Prefix(string p)
{
stack<string> s;
string x,y;
for(int i=0;i<p.length();i++)
{
int a=checkvar(p[i]);
if(a)
{
string k="";
k=k+p[i];
s.push(k);
}
else
{
x=s.top();
s.pop();
y=s.top();
s.pop();
string t="";
t=t+p[i]+y+x;
s.push(t);
}
}
string t=s.top();
return t;
}
};
int main()
{
Parse p;
ifstream infile("f.txt");
string st;
while(getline(infile,st))
{
p.a=st;
string str=p.infixToPostfix();
double ans=p.Postfix2Eval(str);
cout<<endl<<"infix "<<"prefix "<<"postfix "<<"value ";
cout<<st<<" ";
cout<<p.Postfix2Prefix(str)<<" ";
cout<<str<<" ";
cout<<ans<<endl;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.