Q. Write an algorithm design Idea for the following c++ code. The code is about calculate the value of a mathematical expression (Binary tree).
#include #include #include #include using namespace std; //checking for precedance of the operators in the stack: // multiplication and division has the highest priority , then comes addition and subtraction int precedence(char t) { if (t == '*' || t == '/') 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 exoression value and return it. int calculate(string tokens){ int i; stack values; stack 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 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:"<>math_exp; math_exp = math_exp.substr(1 , math_exp.size()-2); cout<<" The value is:"<
