Need help with stack template project for C++ please and thank you. PLEASE SEND
ID: 666199 • Letter: N
Question
Need help with stack template project for C++ please and thank you. PLEASE SEND CORRECT CODE BY THE DIRECTIONS WITH SCREENSHOT OUTPUT. I have yet to get a correct answer so far. Please semd it correctly so I do not get confused on making it work and the concepts. The input.txt is in the dropbox link below.
https://www.dropbox.com/sh/36sxpfkktf7rawv/AABiPMaEmnPVSsVlR65Jr7S6a?dl=0
For the last program of the summer, we'll be writing a simple expression evaluator that uses a stack template. We use the usual rules about precedence to resolve which operation should be done first if an expression is potentially ambiguous:
A + B + C // is this (A+B) + C, or A + (B+C)? Addition is left-associative, do A+B first, then add C A – B + C // is this (A-B) + C, or A – (B+C)? Usual rule is left-to-right, do A-B first then add C A + B – C // likewise, this is (A+B) – C A + B*C // Multiplication is higher priority, do B*C first, then add A and so on…
Where it gets fun is when it's something like this: A + B * C / D + E / F * G + H One solution, of course, is to demand that developers remember the exact order of evaluation—if * and / operations are on the same line, is it the * are done then the /, or the / then the *, or left to right? (Answer: different compilers implement it differently, regardless of what the standard says). Thus the usual practical solution is to allow parentheses to allow the developer to specify exactly what is meant: (A + (B * C) / ((D + E) / F) * (G + H)) This has 2 advantages: all compilers follow the “innermost parentheses first” rule and will evaluate the expression the same way, and we can write expressions that would require intermediate variables without them, such as (B*C)/((D+E)/F).
What if the developer didn't fully parenthesize the expression? Then the compiler can insert parentheses, using the rules of the language, and then evaluate the parenthesized expression that results. And yes, that's how it done. Rather than writing code to evaluate a possibly-ambiguous expression, code that inserts characters (parentheses) into a string, and then code to evaluate a fully parenthesized expression, is easier to write, easier to test and debug (because the parts can be tested separately).
For this program we're writing the second part of this: Given a string containing a fully parenthesized algebraic expression, evaluate the expression.
For this program, we'll make a few simplifying assumptions; primarily, all numbers will be single-digit integers >= 0, so they'll be single characters, and the expected results will be integers. (So all operations, including division, will be integer division, with fractions dropped).
So how's this done? To carry this out, 2 stacks are needed, 1 for numbers (ints) and the other for operators (chars). Thus, a template stack is needed. Input is a fully-parenthesized algebraic expression.
The evaluation algorithm is as follows: For each character in the expression: if the character is any of: ( + - * / Push this character on to the operators stack If the character is any of: 0 1 2 3 4 5 6 7 8 9 Convert to an int and push onto the numbers stack (remember that int(‘0’) is NOT the integer 0!) If the character is: ) Pop right operand from numbers stack If the numbers stack is empty, declare an error and end processing of this expression Pop left operand from numbers stack If the numbers stack is empty, declare an error and end processing of this expression Pop operator from operator stack If the operator stack is empty, declare an error and end processing of this expression Carry out operation Push result onto numbers stack Top of operator stack should be the corresponding ( If so, remove it If it's not a left-parenthesis, declare an error and end processing of this expression At end of expression, the following conditions should hold: The operator stack is empty The numbers stack has exactly one value: the value of the expression
You are given an input file containing several expressions, some of them valid, some not. Output is to the screen; for each expression, either the value of the expression or an “invalid expression” message.
Development notes: • Write a template List class. The class should contain the following methods:
push_back(item) push_front(item) insert(item) // assumes list is already sorted, places in order sort() size() clear() pop_front() // removes first item, returns nothing pop_back() // removes last item, returns nothing front() // returns first item, does not alter list back() // returns last item, does not alter list remove(item) // removes 1st occurrence found in list remove_all(item) // removes all occurrences in list is_present(item) const // returns true if item is anywhere in list, false otherwise
As part of the List class, declare a ListException class that can be thrown on a list error (such as attempting to remove something from an empty list, etc) • The stack class will be a wrapper for the list class, exposing only a limited set of of this functionality: push(item), which calls push_back top(), which calls back() pop(), which calls pop_back() size(), clear(), and is_present() all call the corresponding list methods.
• As part of your stack class, define a StackException class that can be thrown on stack overflow or underflow. This can simply be a catch block that catches a ListException and throws a StackException as its action.
• Your program should print error messages for mismatched parentheses (at end of processing a right-parenthesis, the top character on the operator stack is anything other than the corresponding left parenthesis), invalid character in input, or “invalid expression” for anything else.
Example of input and final output should look like this:
Input (input.txt):
(1 + 1)
((7+5)/2) (
(3*4)+ 1)
(1 + * 1)
((7+5)/2))
(((3*4)+ 1)
((7+5)/2 3)
((7$5)/2)
(((9+3)*((3+1)/(1+1)))/4)
Output (to screen):
2
6
13
Mismatched parentheses in expression. Invalid expression.
Stack error in Evaluate(): Stack error on item access Invalid expression.
Invalid expression.
Invalid expression.
Invalid character in input: $ Invalid expression.
6
Press any key to continue . . .
Explanation / Answer
Answer:
Main.cpp
#include <iostream>
#include <iomanip>
#include <fstream>
#include <ctype.h>
using namespace std;
#include "stack.h"
bool writeOperate1(Stack<int>&, ofstream&, char);
void writePush1(Stack<int>&, ofstream&, char[]);
void getResult1(Stack<int>&, ofstream&, bool);
int main()
{
char token1[3];
bool valid = true;
Stack<int> stack(10);
ifstream expressions1;
expressions1.open("input.txt");
while(expressions1 >> token1)
{
if(token1[0] == ';')
getResult1(stack, results, valid);
else if(isdigit(token1[0]))
writePush1(stack, results, token1);
else if(ispunct(token1[0]))
valid = writeOperate1(stack, results, token1[0]);
}
return 0;
}
void writePush1(Stack<int>& stack, ofstream& file, char* numStr)
{
int number = atoi(numberStr);
cout << numberStr << " ";
stack.push(number);
file << "(Token: " << numberStr << left << setfill(' ') << setw(15) << ")" ;
file << "Push " << numberStr << endl;
}
bool writeOperate1(Stack<int>& stack, ofstream& file, char op)
{
int number1,
number2;
int total1 = 0;
bool success = false;
cout << op << " ";
stack.pop(number2);
if(stack.pop(number1))
{
switch (op)
{
case '+':
total1 = number1 + number2;
break;
case '-':
total1 = number1 - number2;
break;
case '*':
total1 = number1 * number2;
break;
case '/':
total1 = number1 / number2;
break;
case '%':
total1 = number1 % number2;
break;
}
stack.push(total1);
success = true;
}
file << "(Token: " << op << left << setfill(' ') << setw(15) << ")";
file << "Pop " << left << setfill(' ') << setw(15) << number1;
file << "Pop " << left << setfill(' ') << setw(15) << number2;
file << "Push " << total1 << endl;
return success;
}
void getResult1(Stack<int>& stack, ofstream& file, bool success)
{
int total1;
int size1= stack.getSize();
if(size1== 1 && success)
{
stack.pop(total1);
cout << "= " << total1 << endl;
file << " ";
file << left << setfill(' ') << setw(15) << "Valid: ";
file << "result = " << total1;
size--;
}
else
{
cout << "= Invalid" << endl;
file << " ";
file << "RPN Expressions is Invalid";
}
file << " ";
for(int i = 0; i < size; i++)
{
stack.pop(total1);
}
}
Stack.h
#ifndef STACK_H
#define STACK_H
template<typename TYPE1>
class Stack
{
private:
TYPE1* stack;
int top1,
capacity1;
public:
Stack(int c1 = 100);
~Stack();
bool push1(const TYPE1&);
bool pop1(TYPE1&);
bool peek1 (TYPE1&) const;
bool isEmpty() const;
bool isFull() const;
int getSize1() const;
};
template<typename TYPE1>
Stack<TYPE1>::Stack(int c1)
{
capacity1 = c1;
stack1 = new(nothrow) TYPE1[capacity1];
top1 = -1;
};
template<typename TYPE1>
Stack<TYPE1>::~Stack()
{
delete[] stack;
capacity1= 0;
top1 = -1;
};
template<typename TYPE1>
bool Stack<TYPE1>::push1(const TYPE1& dataIn)
{
bool success = false;
if(top1 + 1 < capacity1)
{
top1++;
stack[top1] = dataIn;
success = true;
}
return success;
};
template<typename TYPE1>
bool Stack<TYPE1>::pop1(TYPE& dataOut1)
{
bool success = false;
if(top1 > -1)
{
dataOut1 = stack[top1];
top1--;
success = true;
}
return success;
};
template<typename TYPE1>
bool Stack<TYPE1>::peek1(TYPE& dataOut1) const
{
bool success = false;
if(top1 > -1)
{
dataOut1 = stack[top1];
success = true;
}
return success;
};
template<typename TYPE1>
int Stack<TYPE1>::getSize1() const
{
return (top1 + 1);
};
template<typename TYPE1>
bool Stack<TYPE1>::isEmpty() const
{
return (top == -1);
};
template<typename TYPE1>
bool Stack<TYPE1>::isFull() const
{
return (top1 + 1 == capacity1);
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.