Calculate the value of a mathematical expression (Binary Tree) Problem description] iven a mathematical expression, calculate its value by constructing binary tre lathematical operations in the expression indude +, -, * 1, 0. Th athematical expression begins and ends with #. Output the postorde aversal sequence of the constructed binary tree at the same time. Because th inary tree corresponding to a mathematical expression is not unique, th reorder traversal sequence is also not unique. Any feasible preorder traversa equence is ok. Basic requirements and Example] /hat you need to show in the terminal(the back part is outputted by yo nd the blue part is inputted by the user, i.e, teacher): ease input the mathematical expression: 1+2*(4-3)-8/2#
Please write the
#include<iostream>
#include<string>
#include<stack>
#include <algorithm>
using namespace std;
//checking for precedence of the operators in the stack:
// As per priority basis multiplication and division has the highest priority,than addition and subtraction
int precedence(char t)
{
if (t == '*' || t == '/')//priorities check
return 2;
else if (t == '+' || t == '-')
return 1;
else
return -1;
}
//while calculating the value of given expression, through the below function we will apply the operation and return the integer value
int applyOp(int a, int b, char op){
switch(op){
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}
//this function calculates the expression value and return it.
int calculate(string tokens){
int i;
stack <int> values;
stack <char> ops;
for(i = 0; i < tokens.length(); i++){
if(tokens[i] == '('){
ops.push(tokens[i]);
}
else if(isdigit(tokens[i])){
int val = 0;
while(i < tokens.length() &&
isdigit(tokens[i]))
{
val = (val*10) + (tokens[i]-'0');
i++;
}
values.push(val);
i--;
}
else if(tokens[i] == ')')
{
while(!ops.empty() && ops.top() != '(')
{
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
if(!ops.empty())
ops.pop();
}
else
{
while(!ops.empty() && precedence(ops.top())
>= precedence(tokens[i])){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
ops.push(tokens[i]);
}
}
while(!ops.empty()){
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
return values.top();
}
//this function converts the infix expression to postfix expression and this postfix expression is again used to find the prefix expression
string inpost(string s)
{
string result = "\0";
stack<char> st;
char c;
for (int i = 0; i < s.size(); i++)
{
c = s[i];
if (c >= '0' && c <= '9')
result += c;
else if (c == '(')
st.push(c);
else if (c == ')')
{
while (st.top() != '(')
{
result += st.top();
st.pop();
}
st.pop();
}
else
{
while (!st.empty() && precedence(s[i]) < precedence(st.top()))
{
result += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty())
{
result += st.top();
st.pop();
}
return result;
}
//convert(string) function prints the prefix expression on the terminal
void convert(string infix)
{
int l = infix.size();
reverse(infix.begin(), infix.end());
for (int i = 0; i < l; i++) {
if (infix[i] == '(') {
infix[i] = ')';
i++;
}
else if (infix[i] == ')') {
infix[i] = '(';
i++;
}
}
string prefix = inpost(infix);
reverse(prefix.begin(), prefix.end());
cout<<"The postorder traversal sequence is:"<<endl;
cout<<prefix;
}
int main(){
string math_exp;
cout<<"Please input the mathematical expression:"<<endl;
cin>>math_exp;
math_exp = math_exp.substr(1 , math_exp.size()-2);
cout<<"The value is:"<<endl;
cout<<calculate(math_exp)<<endl;
convert(math_exp);
return 0;
}
![8. Calculate the value of a mathematical expression (Binary Tree)
[Problem description]
Given a mathematical expression, calculate its value by constructing binary tree.
Mathematical operations in the expression indude +, , * 1, 0 The
mathematical expression begins and ends with #. Output the postorder
traversal sequence of the constructed binary tree at the same time. Because the
binary tree corresponding to a mathematical expression is not unique, the
preorder traversal sequence is also not unique. Any feasible preorder traversal
sequence is ok.
[Basic requirements and Example]
What you need to show in the terminal(the back part is outputted by you
and the blue part is inputted by the user, i.e., teacher):
Please input the mathematical expression:
#1+2*(4-3)-8/2#
The value is:
-1
The postorder traversal sequence is:
-+1*2-43/82](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fceb76ecc-c617-4dcc-8586-e89b08b5b658%2F27927ca7-528a-4bfe-b3e9-b29faf119fb6%2Fbn6o1y_processed.png&w=3840&q=75)
Step by step
Solved in 2 steps
