Finding 'sqrt', 'log' and 'abs' in a expression

[Joemeister]

Hello all,

What I am doing is the following:

1. Receiving an expression
2. Instantiating Variables
3. Convert the expression from infix to postfix
4. Evaluate the expression.

Now, in my evaluate function the following operators are working:

+ - * / and ^

I am having trouble to get the following to work: sqrt, abs, and log. Because 'sqrt' is 4 characters long and I am only searching for [i] in my string which is one character. I assume if you can get one of these 3 to work then you can get all 3 to work. So if you can give me advice on how to get this to work I will really appreciate it.

I dont know if I should provide you the code because it is 300 lines.

[Moschops]

C++ strings come with functions to find substrings inside them.

http://www.cplusplus.com/reference/string/string/find/

[L7Sqr]

I've been witnessing your threads evolving as you develop your calculator application over time. You are at the point now that you are wanting to introduce the equivalent of function calls within your input. This has now become, for all intents and purposes, a domain specific language (DSL).

You may want to look into how to build a parser to handle your language in a more consistent way. There are old technologies (flex, bison) and more recent tools (llvm) available for free to do this. Each have decent tutorials and starting points (most likely with examples in the wild for exactly what you want to do).

I'd suggest you consider moving to this more standard approach as you continue to evolve your project. At some point, you will not be able to deconflict the structure of the input with simple string manipulation. A simple example would be how to handle: (2 + sqrt(3 + 6))
When does 3 + 6 get processed in your current design?

[iamthwee]

I disagree, I wouldn't recommend using flex or bison, as this is an assignment and even if you understood it, you wouldn't gain any marks.

Instead a very simple approach can be adopted which allows you to work with single digit characters.

All you need to do, is give those functions an arbitary letter, for example sqrt = #, abs = ~ and log = $.

Then you could still accept the input as sqrt(5+2), log(7), abs(-1) but before you do any processing you do a string replace.

So sqrt(25) + log(7) - abs(-1) would be changed into #(25) + $(7) - ~(-1). That way the end user never needs to know what those strange symbols mean, but your program can easily handle these new functions.

Of course I'm assuming these are the only extra three functions you would need to handle.

I think that will get you out of the woods so to speak.

[iamthwee]

To illustrate my point please see:

http://stackoverflow.com/questions/20759028/infix-to-postfix-math-functionsin-c

Don't be afraid to post your code 300 lines is nothing really.

[Joemeister]

Yeah, I also thought of the idea of setting "sqrt" = '#' and then when sqrt is found in the expression it refers to the # when doing the calculation? Or something like that.

Okay, here goes...

Expression::Expression(string expr)
{
        originalExpr = shuntingYard(expr);
        modifiedExpr = originalExpr;
}

Expression::~Expression()
{
}

void Expression::instantiateVariable(char var, int val)
{
    string valA;
    valA = numberToString(val);
    for(int i = 0; i < originalExpr.length();i++)
    {
        if(originalExpr[i] == var)
        {
            modifiedExpr.replace(i, 1, valA);
        }
    }
}

string Expression::numberToString(int number)
{
    ostringstream ss;
    ss << number;
    return ss.str();
}

string Expression::shuntingYard(string modifiedExpr)
{
    // Declaring a Stack from Standard template library in C++.
    stack<char> S;

    //Initialize postfix as empty string.
    string postfix = "";
    for(unsigned int i = 0; i< modifiedExpr.length(); i++)
    {
        //Test for white space
        if(modifiedExpr[i] == ' ')
        {
            continue;
        }

        //If character is operator, pop two elements from stack, perform operation and push the result back.
        else if(IsOperator(modifiedExpr[i]))
        {
            while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),modifiedExpr[i]))
            {
                postfix+= S.top();
                S.pop();
            }
            S.push(modifiedExpr[i]);
        }

        //Else if character is an operand
        else if(IsOperand(modifiedExpr[i]))
        {
            postfix += modifiedExpr[i];
        }

        else if (modifiedExpr[i] == '(')
        {
            S.push(modifiedExpr[i]);
        }

        else if(modifiedExpr[i] == ')')
        {
            while(!S.empty() && S.top() !=  '(') {
                postfix += S.top();
                S.pop();
            }
            S.pop();
        }
    }

    while(!S.empty()) {
        postfix += S.top();
        S.pop();
    }

    return postfix;

}


// Function to verify whether a character is a letter or a digit
bool Expression::IsOperand(char A)
{
    if(A >= '0' && A <= '9')
    {
        return true;
    }
    if(A >= 'a' && A <= 'z')
    {
        return true;
    }
    if(A >= 'A' && A <= 'Z')
    {
        return true;
    }
    else
    {
        return false;
    }
}

// Function to verify whether a character is operator symbol or not.
bool Expression::IsOperator(char C)
{
    if(C == '+' || C == '-' || C == '*' || C == '/' || C == 'sqrt' || C == 'log' || C == 'abs' || C == '~')
    {
        return true;
    }
    else
    {
        return false;
    }
}

// Function to verify whether an operator is right associative or not.
int Expression::IsRightAssociative(char opA)
{
    //POWER
    if(opA == '^')
    {
        return true;
    }

    //SQUARE ROOT
    if(opA == 'sqrt')
    {
        return true;
    }

    //LOG
    if(opA == 'log')
    {
        return true;
    }

    //ABSOLUTE
    if(opA == 'abs')
    {
        return true;
    }

    //NEGATE
    if(opA == '~')
    {
        return true;
    }
    else
    {
        return false;
    }
}

// Function to get weight of an operator. An operator with higher weight will have higher precedence.
int Expression::GetOperatorWeight(char opB)
{
    int weight = -1;
    switch(opB)
    {
    case '+':
    case '-':
        weight = 1;
    case '*':
    case '/':
        weight = 2;
    case '^':
        weight = 3;
    case 'sqrt':
        weight = 4;
    case 'log':
        weight = 5;
    case 'abs':
        weight = 5;
    case '~':
        weight = 6;
    }
    return weight;
}

// Function to perform an operation and return output.
int Expression::HasHigherPrecedence(char op1, char op2)
{
    int op1Weight = GetOperatorWeight(op1);
    int op2Weight = GetOperatorWeight(op2);

    if(op1Weight == op2Weight)
    {
        if(IsRightAssociative(op1))
                {
                    return false;
                }
        else
                {
                    return true;
                }
    }
    return op1Weight > op2Weight ?  true: false;
}

int Expression::evaluate()
{
    stack<int> resultStack;
    int length = modifiedExpr.length();

    for (int i = 0; i < length; i++)
    {
        if ((modifiedExpr[i] == '+') || (modifiedExpr[i] == '-') || (modifiedExpr[i] == '*') || (modifiedExpr[i] == '/') || (modifiedExpr[i] == '^') || (modifiedExpr[i] == '~') || (modifiedExpr[i] == 'sqrt') || (modifiedExpr[i] == 'log') || (modifiedExpr[i] == 'abs'))
        {
            int p1 = resultStack.top(); resultStack.pop();
            int p2 = resultStack.top(); resultStack.pop();
            int result = doTheOperation(p1, p2, modifiedExpr[i]);
            resultStack.push(result);
        }
        else if ((modifiedExpr[i] >= '0') || (modifiedExpr[i] <= '9'))
        {
            resultStack.push((int)(modifiedExpr[i] - '0'));      //How to get value higher than 9 in the array????
        }
        else
        {
        }
    }
    return resultStack.top();
}

//The operations that must be done if a specific operator is found in the string
int Expression::doTheOperation(int left, int right, char op)
{
    switch (op)
    {
        case '+':
            return (left + right);
        case '-':
            return (right - left);
        case '*':
            return (left * right);
        case '/':
            return (right / left);
        case '^':
            return (pow(right,left));
        case '~':
            return (right * -1);
        case 'sqrt':
            if(right < 0)
            {
                string temp = "Square root of a negative number.";
                throw temp;
            }
            else
            {
                return (sqrt(right)) ;
            }
        case 'log':
            if (right < 0)
            {
                string temp = "Error. Not able to get the log of zero.";
                throw temp;
            }
            else
            {
                int temp = log10(right);
                return ceil(temp);
            }
        case 'abs':
            if (right < 0)
            {
                return (right*-1);
            }
            else
            {
                return right;
            }

        default:
            return -1;
    }
    return -1;
}

[Joemeister]

Sorry if it's a lot to read but focus on the following functions

1. IsOperator()
2. IsRightAssociative()
3. GetOperatorWeight()
4. evaluate()
5. doTheOperation()

[iamthwee]

OK I'll see if I can look at this tonight.

[NathanOliver]

You have:

bool Expression::IsOperator(char C)
{
    if(C == '+' || C == '-' || C == '*' || C == '/' || C == 'sqrt' || C == 'log' || C == 'abs' || C == '~')
    {
        return true;
    }
    else
    {
        return false;
    }
}

Which makes no sense. A char cannot be more then one letter. You need to replace the function calls with single characters before you pass them shuntingYard().

[L7Sqr]

I disagree, I wouldn't recommend using flex or bison, as this is an assignment and even if you understood it, you wouldn't gain any marks.

I'm not suggesting to do this for extra marks; it is a code clarity and maintenance issue.

I was not assuming this was an assignment. However, if it is there should exist progress toward one of two goals:

1. Provide exposure to, and experience with, a simple and well-defined problem
2. Work as a portion of a larger set of problems intended to grow to a more substantial effort.

What I see is evident of #2 (if this is, in fact, an assignment). The Shunting Yard algorithm is an assignment to take infix to postfix. It does not handle things such as function calls. To do that properly you need to provide a stateful parser.

Replacing function names with symbols does not change the problem. sqrt(3 + 5) is equivalent to #(3 + 5). You need to handle the expression within the call separately than the outer expression. Moreover, the symbols sqrt(3 + 5) should be considered a single node in the graph (or stack, as is being used in this exercise).

At some point string replace operations are insufficient to deal with the parsing problem. If this is an assignment there should be clear guidelines on the operations to be supported and the final language to be used.

@Joemeister, perhaps you could provide some clarification.

[iamthwee]

Hi joe,

Please provide the full code, you've omitted the class declaration.

E.g

class Expression
{
public:
    Expression(string expr); //default constructor
    ~Expression();//default destructor
};

Then I can walk you through the changes.

[iamthwee]

I'm not suggesting to do this for extra marks; it is a code clarity and maintenance issue.

Incorrect, as this is an assignment using flex or bison is unhelpful and requires a further learning curve... As a free standing project with no restrictions you may have a point.

You need to handle the expression within the call separately than the outer expression.

Incorrect, all you would need to do is expand the class accordingly, and add a precedence operator for sqrt or abs or log, unless that's what you meant?

E.g

sqrt(5+5) + 2

would be after a simple string replace:

#(5 + 5) + 2 -where # denotes square root

The postfix expression would be...

5 5 + # 2 +

Similarily, the same process can be achieved with the absolute function or log function.

[L7Sqr]

flex or bison is unhelpful and requires a further learning curve

So I went back and looked at the related posts to this topic and saw that there was a reply that said that this was an assignment. I missed that. For an assignment, yes, flex and bison would be too much.

However, I still maintain that parsing this input according to tokens is the proper way to manage the assignment - not replacing function names with a single character (you alluded to this yourself).

Converting sqrt(9) + 2 into #(9) + 2 has little benefit (that I can see). What is the benefit of 9 # 2 + over 9 sqrt 2 +? It basically requires the second pass through the stack to do the reverse transformation when calculating the result.

The postfix expression would be...

As far as the functions being handled by the first pass; your example works just fine so long as there is a single argument. What happens when you need to support pow(2,4)? Or log(16,2)?

My point is that basic string manipulation will only get you so far. It is probably the case that it will be sufficient for this assignment and I don't want to detract from the original thread too much but it is an important point to understand.

[iamthwee]

What is the benefit of 9 # 2 + over 9 sqrt 2 +?

There is no benefit from a purely theoretical point of view, but the OP is using single chars to parse his stack. Therefore, by converting the string sqrt to a single character allows him to work within his current framework. Otherwise he would have to extend his class to handle tokens and in this instance you're absolutely right. Generally, string tokens are right way to go.

What happens when you need to support pow(2,4)

He already has the power function working and it isn't written as you have written it, it is written as 2^4 which happily works using the shunting algorithm, the same could be said of 16 log 2

and I don't want to detract from the original thread too much but it is an important point to understand.

Yes I agree, you have made quite a few valid points I guess I was just being a bit anal about the level of the OP and what he is capable of, I guess this is subjective.

[マーズ maazu]

Greetings all, some one recommended earlier to improve the parser, instead of handling char by char, the improved parser will handle entire tokens. Then a template function to convert string tokens into integers/doubles is used to handle all inputs.

At present, my evaluate() only handles BODMAS, I think this program should stick to Ford and Topps intentions of teaching data structures. Another problem with introducing sqrt() is the fractions, any ideas on dealing with remainders/quotients without losing precision due to rounding off integers?

[iamthwee]

I don't think you can avoid rounding errors unless you wrote some sort of fraction class using Euclid's GCD

[マーズ maazu]

It is done. It can use double. It can do scientific mode. It only use 40Kbytes.