**Complete this problem in the LANGUAGE SCHEME (R5RS)** 2. (A continuation of th
ID: 3603827 • Letter: #
Question
**Complete this problem in the LANGUAGE SCHEME (R5RS)**
2. (A continuation of the previous problem; pre-, in-, and post-order traversal.) Such trees can be traversed recursively (which you will have done in the solution to your previous problem). In this problem, you will print out the expression associated with a parse tree, using several different conventions for writing arithmetic expressions. There are three conventional orders in which nodes and subtrees can be "visited" during a recursive traversal of a tree. Note that at each node, there three tasks to carry out: visit (in this case, that means print out) the node, traverse the left subtree, and traverse the right subtree. For instance, an inorder traversal of a binary tree wll 1) recursively traverse the left subtree, 2) visit the node, and then 3) recursively traverse the right subtree.Explanation / Answer
Hope this would be of help
#include <iostream>
using namespace std;
template <class type>
class Node {
public:
type data;
Node* link;
Node(type x)
{
data = x;
link = NULL;
}
};
template <class T>
class Stack
{
private:
Node<T>* top;
public:
Stack()
{
top = NULL;
}
void push(T x)
{
Node<T>* temp = new Node<T>(x);
if(top == NULL)
top = temp;
else {
temp->link = top;
top = temp;
}
}
bool pop(T& x)
{
if(top == NULL)
return false;
else {
x = top->data;
Node<T>* temp = top;
top = top->link;
delete temp;
return true;
}
}
bool peek(T& x)
{
if(top == NULL)
return false;
else {
x = top->data;
return true;
}
}
void print()
{
Stack<T> s;
T k;
while(pop(k)) {
cout << k;
s.push(k);
}
while(s.pop(k))
push(k);
}
~Stack()
{
T k;
while(pop(k))
;
}
};
class ConverterSolver
{
private:
char* postfix;
int postfixSize;
char* variables;
int varNum;
double* varValue;
bool isHigher(char a, char b)
{
int x, y;
if(a == '(')
return false;
if((a == '+') || (a == '-'))
x = 1;
else
x = 2;
if((b == '+') || (b == '-'))
y = 1;
else
y = 2;
return (x >= y);
}
public:
ConverterSolver(char A[], int e)
{
postfixSize = 0;
varNum = 0;
postfix = new char[e];
variables = new char[e];
varValue = new double[e];
Stack<char> op;
char cur, temp;
bool found;
for(int i = 0; i < e; i++) {
cur = A[i];
//cout << "cur: " << cur << endl;
switch(cur) {
case '(':
op.push(cur);
break;
case '+':
case '-':
case '*':
case '/':
if(op.peek(temp))
while(isHigher(temp, cur)) {
op.pop(temp);
postfix[postfixSize++] = temp;
if(!op.peek(temp))
break;
}
op.push(cur);
break;
case ')':
op.peek(temp);
while(temp != '(') {
op.pop(temp);
postfix[postfixSize++] = temp;
op.peek(temp);
}
op.pop(temp);
break;
default:
postfix[postfixSize++] = cur;
found = false;
for(int u = 0; u < varNum; u++)
if(cur == variables[u])
found = true;
if(!found)
variables[varNum++] = cur;
break;
}
/*
cout << "stack: ";
op.print();
cout << " postfix: ";
for(int h = 0; h < postfixSize; h++)
cout << postfix[h];
cout << " ";
*/
}
while(op.pop(temp))
postfix[postfixSize++] = temp;
postfix[postfixSize] = '';
}
void printPostfix()
{
cout << "Postfix " << postfix << endl;
}
void solvePostFix()
{
int i, count = 0;
char cur;
double x, y, z;
cout << "Enter values ";
for(i = 0; i < varNum; i++) {
cout << variables[i] << " = ";
cin >> varValue[i];
}
Stack<double> ans;
for(i = 0; i < postfixSize; i++) {
cur = postfix[i];
switch(cur) {
case '+':
case '-':
case '*':
case '/':
ans.pop(y);
ans.pop(x);
if(cur == '+')
z = x + y;
else if(cur == '-')
z = x - y;
else if(cur == '*')
z = x * y;
else
z = x / y;
ans.push(z);
break;
default:
ans.push(varValue[count++]);
}
}
ans.pop(z);
cout << "Result " << z << endl;
}
~ConverterSolver()
{
delete[] postfix;
delete[] variables;
delete[] varValue;
postfix = variables = NULL;
varValue = NULL;
}
};
int main()
{
char c;
char infix[100];
int size = 0;
cout << "Enter an infix expression with ($) at the end: ";
cin >> c;
while(c != '$') {
infix[size++] = c;
cin >> c;
}
ConverterSolver k(infix, size);
k.printPostfix();
k.solvePostFix();
cout << " ";
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.