For this assignment you need to use a stack to implement a simple Arithmetic Ope
ID: 641526 • Letter: F
Question
For this assignment you need to use a stack to implement a simple Arithmetic Operation Analyzer, called "parseArithmetic", which is a member function in the "StackLink" class. The function signature is as follows:
bool parseArithmetic(const string s)
The input argument is a string s, which represents a sequence of arithmetic expression in the "PostFix" style. For example,
s = "3 4 5 * 6 / +" (The corresponding infix is 3 + 4 * 5 / 6)
So here we use space " " to separate each "operator" or "operand".
If the input expression s is valid expression, this function should return true, otherwise returns false.
As a simpler version of arithmetic parser, we assume there are only FOUR operators: "+ - * / ". The operands can only be letters "a - z", or "A - Z" and numbers "0 - 9". So if it detects any other illegal characters, such as "," "&", "$", "", "!"..., it should terminate the function immediately by returning false.
Notice:
1. Since this function "parseArithmetic" is a member function of "StackLink" class. You should use this class to store the data. This means when you extract every character c from the expression s, if c is a legal character, you need to push c into the stack provided by "StackLink" class rather than creating a new stack inside the function body "parseArithmetic".
2. Again, similar to assignment 1, you down the framework file provided in the attachment. You just need to add your code in the area marked as "//implementation here".
3. In the main function, it provides several testing cases: if the input s is correct, it prints out 1; otherwise, it prints out 0. Since you have not implemented it yet, so it print out 1 by default. After your implementation, it should print out the one as indicated in the comment besides each line.
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
struct Node{
char item;
Node *link;
};
class StackLink{
private:
Node *top;
int size;
public:
StackLink(){
top = NULL;
size = 0;
}
void push(char x)
{
Node* temp = new Node;
temp->item = x;
temp->link = top;
top = temp;
size++;
}
void pop()
{
Node* temp;
if(top == NULL)
return;
temp = top;
top = top->link;
delete temp;
size--;
}
char peek()
{
return top->item;
}
/*Analyze whether the input string expression has a correct grammar in terms of arithmetic operations*/
bool parseArithmetic(const string s)
{
//implementation here
return true;
}
void printStack()
{
printf("The stack (size %d): ", size);
Node *p = top;
while(p != NULL)
{
printf("%c, ", p->item);
p = p->link;
}
printf(" ");
}
};
int main(int argc, const char * argv[]) {
StackLink stack;
cout<<stack.parseArithmetic("3 4 5 * 6 / +")<<endl; //1
cout<<stack.parseArithmetic("3 4 - 5 * 6 / +")<<endl; //0
cout<<stack.parseArithmetic("3 4 5 * 6 / 9 +")<<endl; //0
cout<<stack.parseArithmetic("300 23 + 43 21 - * 84 7 + /")<<endl; //1
cout<<stack.parseArithmetic("a 23 + c 21 - * 84 7 + /")<<endl; //1
cout<<stack.parseArithmetic("a % + c 21 - * 84 7 + /")<<endl; //0
cout<<stack.parseArithmetic("E 8 + d 5 - * 3 2
Explanation / Answer
Program Code:
#include <iostream>
#include <string.h>
using namespace std; //should not be in header file - just to remove std:: below
template <class T>
class stack {
class node {
public:
T data;
node* next;
node(T const &d) : data(d), next(0) {}
node() : data(0), next(0) {}
};
node *top;
public:
stack() : top(0) {}
stack(const stack& s) {
node* nextnode = s.top;
while(nextnode != 0)
{
node* newnode = new node;
newnode->data = nextnode->data;
newnode->next = nextnode->next;
nextnode=nextnode->next;
top = newnode;
cout<<"copy constructed "<< newnode->data <<endl;
}
}
stack& operator=(const stack& s) {
node* nextnode = s.top;
while(nextnode != 0)
{
node* newnode = new node;
newnode->data = nextnode->data;
newnode->next = nextnode->next;
top = newnode;
cout<<"operator = "<< newnode->data <<endl;
delete nextnode;
nextnode=nextnode->next;
}
}
/*~stack()
{
if(top)
{
node* current = top;
node* next = 0;
while (current != 0)
{
next = current->next;
cout << "dtor deleting node " << current->data << endl;
delete current;
current = next;
}
}
}*/
void push(const T& item)
{
node *n=new node;
n->data=item;
n->next = top;
top=n;
cout<<"Push new'd node "<< n->data << endl;
}
void pop()
{
node *n=top;
top=top->next;
n->next=NULL;
cout<<"Pop delete'd node "<< n->data << endl;
delete n;
}
void print()
{
node *n= top;
while(n != 0)
{
cout<<n->data<<endl;
n=n->next;
}
}
};
class StackLink
{
stack<char> st;
public:
StackLink()
{
}
bool parseArithmetic(const string s)
{
for(int i=0;i<s.size();i++)
{
if(isalpha(s[i]))
st.push(s[i]);
else if(isdigit(s[i]))
st.push(s[i]);
else if(s[i]=='+')
st.push(s[i]);
else if(s[i]=='-')
st.push(s[i]);
else if(s[i]=='*')
st.push(s[i]);
else if(s[i]=='/')
st.push(s[i]);
else if(s[i]==' ')
cout<<"";
else
{
cout<<" Sorry! expression can not be evaluated."<<endl;
}
}
return true;
}
};
//main function
int main()
{
StackLink s;
cout<<s.parseArithmetic("5 4 3 * 6 / +")<<endl;
return 0;
}
Sample output:
Sample output:
Push new'd node 5
Push new'd node 4
Push new'd node 3
Push new'd node *
Push new'd node 6
Push new'd node /
Push new'd node +
1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.