Programming Assignment 2 In this project, you will write a program that takes as
ID: 3698685 • Letter: P
Question
Programming Assignment 2
In this project, you will write a program that takes as input an arithmetic expression and should do the following:
Check that the expression is well formed: that means the number of opening parenthesis ‘(‘ is equal to closing ones, the operands are numeric characters, the operators are +, -, * or /.
Build the expression tree based on the arithmetic expression. This will take into consideration the priority of some operators over the others. Each node in the tree has as value a number or a string. In particular, leaf nodes have number values while intermediary nodes have a string value.
Evaluate the outcome of the whole expression by traversing the tree (using one variant of depth-first search) starting with leaf nodes and evaluating each branch until you get the result.
Example: expression = (((9+1)/2)*3)-4
This expression is well-formed because the number of ‘(‘ is equal to the number of ‘)’, operands are numeric characters and operators are the pre-defined ones
For example, expression = (((9+1)/2)*3)-4))) is not a valid expression because it has extra ‘)’. Also expression = (((9+1)/2)*3)-a))) is not valid because a is alphabetical character. expression = (((9+1)/2)*3)&4))) is not valid because & is not among the pre-defined operators
The resulting tree of expression = (((9+1)/2)*3)-4 would be:
To evaluate the outcome of this expression tree, you do a depth-first to retrieve 1, 9 and + to evaluate their outcome, then repeat that recursively until you evaluate the whole tree. The result would be expression = 11.
Explanation / Answer
it is a single program so copy form prog.cpp to end program at the end of the line
first taken input of expression as a string
chek if the expression is valid or not
if valid
convert infix expression to post fix
convert postfix to expression tree
evaluate expression tree
else
print message for invalid input
below is code and comments are added for information.
#code
//--------------------------------------------------------------------prog.cpp----------------------------------------------
#include<bits/stdc++.h>
using namespace std;
//----------------- this part checks if expression is valid or invalid ----------------
bool isvalid(char a){
if((a>='0'&&a<='9') || a=='+'|| a=='-'|| a=='/' || a=='*' || a==')' ||a=='}' || a==']' )
return true;
else false;
}
// function to chek if the expression is balanced and valid or not
// using stack we chek for every openinb bracket we must have a closing brackets
bool checkBalanced(string str) {
stack<char> s;
for(int i =0; i<str.size(); i++){
if(str[i] == '{' || str[i] == '['||str[i] == '(' ){
s.push(str[i]);
}
else if(isvalid(str[i]) == false ){ // this check if we have valid operands or not if invalid return false
cout<<str[i]<<endl;
return false;
}
if(s.empty()){
if(str[i] == '}'||str[i] == ')' || str[i] == ']')
return false;
}
if(!s.empty()){
if(str[i] == '}' && s.top() == '{')
s.pop();
else if(str[i] == ']' && s.top() == '[')
s.pop();
else if(str[i] == ')' && s.top() == '(')
s.pop();
}
}
return s.empty();
// Write your code here
}
//---------------------- converts infix to postfix -------------------------------------------
//Function to return priority of operators
int priority(char c)
{
if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
// convert infix expression to postfix expression
string infixToPostfix(string input)
{
stack<char> s;
int len = input.size(),index=0;
char output[1000];
for(int i = 0; i < len; i++)
{
if((input[i] >= '0' && input[i] <= '9')) {
output[index++] = input[i];
}
else if(input[i] == '(') {
s.push('(');
}
else if(input[i] == ')')
{
// If the scanned character is an ‘)’, pop and to output string from the stack until
//an ‘(‘ is encountered.
while(!s.empty() && s.top() != '(')
{
char c = s.top();
s.pop();
output[index++] = c;
}
if(s.top() == '(')
{
char c = s.top();
s.pop();
}
}
else{
while(!s.empty() && priority(input[i]) <= priority(s.top()))
{
char c = s.top();
s.pop();
output[index++]= c;
}
s.push(input[i]);
}
}
//Pop all the remaining elements from the stack
while(!s.empty())
{
char c = s.top();
s.pop();
output[index++] = c;
}
output[index] = '';
// cout << output << " ";
//copying output into string so that we can return
string ss ="";
int i=0;
while(i < strlen(output)){
ss.push_back(output[i]) ;
i++;
}
return ss;
}
//-------------------------- creates expression tree using postfix expression ---------------------
struct et
{
char value;
et* 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 print inorder traversal for expression tree
void inorder(et *t)
{
if(t)
{
inorder(t->left);
printf("%c ", t->value);
inorder(t->right);
}
}
// A utility function to create a new node of expression tree
et* newNode(int v)
{
et *temp = new et;
temp->left = temp->right = NULL;
temp->value = v;
return temp;
};
// Returns root of constructed tree for given
// postfix expression
et* constructTree(string postfix)
{
stack<et *> st;
et *t, *t1, *t2;
// Traverse through every character of
// input expression
for (int i=0; i<postfix.size(); i++)
{
// If operand, simply push into stack
if (!isOperator(postfix[i]))
{
t = newNode(postfix[i]);
st.push(t);
}
else // operator
{
t = newNode(postfix[i]);
// Pop two top nodes
t1 = st.top(); // Store top
st.pop(); // Remove top
t2 = st.top();
st.pop();
// make them children
t->right = t1;
t->left = t2;
// Add this subexpression to stack
st.push(t);
}
}
// only element will be root of expression
// tree
t = st.top();
st.pop();
return t;
}
//------------------------------------------evaluates the expression tree ---------------------------------
// This function receives a node of the syntax tree
// and recursively evaluates it
int eval(et* root)
{
// empty tree
if (!root)
return 0;
// leaf node i.e, an integer
if (!root->left && !root->right)
return root->value-'0';
// Evaluate left subtree
int l_val = eval(root->left);
// Evaluate right subtree
int r_val = eval(root->right);
// Check which operator to apply
if (root->value== '+')
return l_val+r_val;
if (root->value=='-')
return l_val-r_val;
if (root->value=='*')
return l_val*r_val;
return l_val/r_val;
}
int main(){
// string str1 ="(((9+1)/2)*3)-4";
string str1;
cin>>str1;
int k = checkBalanced(str1);
if(k){
cout<<" It's a valid expression :"<<str1<<endl;
string postfix = infixToPostfix(str1);
cout<<" Postfix conversion is :"<<postfix<<endl;
et* root = constructTree(postfix);
printf(" Infix print of expression tree is :");
inorder(root);
cout<<endl;
cout<<" After evaluation of expression tree we get :";
cout<<eval(root)<<endl;
}
else cout<<" invalid expression ";
}
//-------------------------------------------------------------end program----------------------------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.