Can someone please find the error in code. Gives runtime error "Segmentation Fault" .Expression Tree

Question

Can someone please find the error in code. Gives runtime error "Segmentation Fault" .Expression Tree. I am using a variable for keeping value of expression. It is recursive program. please provide how it can fall into segmentation fault.

This is common problem from tree data structure . Given a full binary expression tree consisting of basic binary operators (+ , – ,*, /) and some integers, Your task is to evaluate the expression tree.

class Solution
{
public:
    /*You are required to complete below method */

    void cal(node* root, stack<string>& sign, stack<int>& num, int& sum)
    {
        if (root == NULL)
        {
            return;
        }

        if (root->data == "+" || root->data == "-" || root->data == "/" || root->data == "*")
        {
            sign.push(root->data);
        }

        else
        {
            num.push(stoi(root->data));
        }

        cal(root->left, sign, num, sum);
        cal(root->right, sign, num, sum);

        int a = num.top();
        num.pop();
        int b = num.top();
        num.pop();
        string sign1 = sign.top();
        sign.pop();

        if (sign1 == "+")
        {
            sum = a + b;
        }

        if (sign1 == "*")
        {
            sum = a * b;
        }

        if (sign1 == "-")
        {
            sum = a - b;
        }

        if (sign1 == "/")
        {
            sum = a / b;
        }

        num.push(sum);
        return;
    }

    int evalTree(node* root)
    {
        // Your code here
        cout << "jh" << endl;
        stack<string> sign;
        stack<int> num;
        int res = 0;
        cal(root, sign, num, res);
        return res;
    }
};

not possible without knowing what type `node` is, how that structure was initialized and what is required result. It's likely But it already obvious that code inherently risks of undefined behavior, `using namespace std` along with user's identifiers _defined_ in `namespace std` — Swift - Friday Pie, Nov 05 '21 at 11:30
1. This is not a [mcve]. Even if I would be willing to debug it for you, I couldn't. 2. This is a good opportunity to learn yourself to debug your code. Debugging is an essential skill of S/W development and worth to be learned. FYI: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/7478597) — Scheff's Cat, Nov 05 '21 at 11:31
@Scheff'sCat I'm pretty sure that it's code from online judge OR badly designed computer-assisted education course. They don't provide whole program, only part you have to tinker with according to description in assignment. That's idea based on 40 year old software development process. The only way to debug is to either run against tests or print something from program. Only way to solve such is an incremental build-up of code with paranoidal sanity checks and checking the output — Swift - Friday Pie, Nov 05 '21 at 11:34
@Swift-FridayPie ...or to resemble the missing parts for local debugging. Concerning _online judge_... I believe it was already mentioned multiple times that competition websites are of limited value to learn S/W development... ;-) — Scheff's Cat, Nov 05 '21 at 11:37
@Scheff'sCat I know that. That should be told to Romanian, Belarusian or , for last couple of years,Russian education standard designers who implement online judge approach as the only way to do test for students, The idea itself is a carbon copy of what schools were doing for years in a number of countries, including such as France or Germany, but was outdated for , as I said, for decades. :P — Swift - Friday Pie, Nov 05 '21 at 11:40
Since this is presumably an interpreter for an expression tree, what do you expect `cal` to do when given a tree such as `{data: 123}` (ie: no operations) — Botje, Nov 05 '21 at 12:48

score 0 · Answer 1 · answered Nov 05 '21 at 13:08

A node can be in one of two forms:

data is a number, no children;
data is an operator, the children are again nodes.

Your code attempts to apply an operator in both scenarios.

Rewrite the function as follows:

    void cal(node* root, stack<string>& sign, stack<int>& num, int& sum) {
        if (root == NULL) {
            return;
        }

        if (root->data == "+" || root->data == "-" || root->data == "/" || root->data == "*") {
            sign.push(root->data);
        } else {
            num.push(stoi(root->data));
            return; // Stop processing here 
        }

        // rest as before
    }

Can someone please find the error in code. Gives runtime error "Segmentation Fault" .Expression Tree

1 Answers1