change the postfix from a string to an array in the first program so that it can
ID: 3912091 • Letter: C
Question
change the postfix from a string to an array in the first program so that it can be taken as a parameter for the second program
First, use the code above to generate a postfix representation
from an infix expression. Then use the code below to crate a
program the creates an expression tree for the postfix representation
which is already done i just need help combineing the two programs so that it will work
using the algorithm given above.
Iterate at least 5 times before ending theprogram with the entry of 999.
#include <iostream>
// C++ program for expression tree
#include<bits/stdc++.h>
using namespace std;
// An expression tree node
struct expressionTree
{
char value;
expressionTree* left, *right;
};
// A utility function to check if 'c'
// is an operator
bool isOperator(char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/' ||
c == '^')
return true;
return false;
}
// Utility function to do inorder traversal
void inorder(expressionTree *t)
{
if(t)
{
inorder(t->left);
printf("%c ", t->value);
inorder(t->right);
}
}
// A utility function to create a new node
expressionTree* newNode(int v)
{
expressionTree *temp = new expressionTree;
temp->left = temp->right = NULL;
temp->value = v;
return temp;
};
// Returns root of constructed tree for given
// postfix expression
expressionTree* constructTree(char postfix[])
{
/*
We loop through input expression and do following for every character.
1) If character is operand push that into stack
2) If character is operator pop two values from stack make them its child and push current node again.
At the end only element of stack will be root of expression tree.
*/
stack<expressionTree *> st;
expressionTree *t, *t1, *t2;
// Traverse through every character of
// input expression
//write your code here
for(int i=0; i<strlen (postfix); i++)
{
//if(!isOperator(postfix[i]))
if(!isOperator(postfix[i]))
{
t=newNode(postfix[i]);
st.push(t);
}
else{
t=newNode(postfix[i]);
t1=st.top();
st.pop();
t2=st.top();
st.pop();
t->left=t2;
t->right=t1;
st.push(t);
}
}
// only element will be root of expression
// tree
t = st.top();
st.pop();
return t;
}
// Driver program to test above
int main()
{
//char postfix[] = "ab+ef*g*-";
// char postfix[] = "3+592*+";
char postfix[] = "123*+";
expressionTree* r = constructTree(postfix);
printf("infix expression is ");
inorder(r);
return 0;
}
Explanation / Answer
Code that change the postfix from a string :
#include <iostream>
#include <stack>
using namespace std;
// funtion to check if character is operator or not
bool isOperator(char x) {
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
// Convert prefix to Postfix expression
string preToPost(string pre_exp) {
stack<string> s;
// length of expression
int length = pre_exp.size();
// reading from right to left
for (int i = length - 1; i >= 0; i--) {
// check if symbol is operator
if (isOperator(pre_exp[i])) {
// pop two operands from stack
string op1 = s.top(); s.pop();
string op2 = s.top(); s.pop();
// concat the operands and operator
string temp = op1 + op2 + pre_exp[i];
// Push string temp back to stack
s.push(temp);
}
// if symbol is an operand
else {
// push the operand to the stack
s.push(string(1, pre_exp[i]));
}
}
// stack contains only the Postfix expression
return s.top();
}
// Driver Code
int main() {
string pre_exp = "*-A/BC-/AKL";
cout << "Postfix : " << preToPost(pre_exp);
return 0;
}
#include <iostream>
#include <stack>
using namespace std;
// funtion to check if character is operator or not
bool isOperator(char x) {
switch (x) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
// Convert prefix to Postfix expression
string preToPost(string pre_exp) {
stack<string> s;
// length of expression
int length = pre_exp.size();
// reading from right to left
for (int i = length - 1; i >= 0; i--) {
// check if symbol is operator
if (isOperator(pre_exp[i])) {
// pop two operands from stack
string op1 = s.top(); s.pop();
string op2 = s.top(); s.pop();
// concat the operands and operator
string temp = op1 + op2 + pre_exp[i];
// Push string temp back to stack
s.push(temp);
}
// if symbol is an operand
else {
// push the operand to the stack
s.push(string(1, pre_exp[i]));
}
}
// stack contains only the Postfix expression
return s.top();
}
// Driver Code
int main() {
string pre_exp = "*-A/BC-/AKL";
cout << "Postfix : " << preToPost(pre_exp);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.