Shunting Yard and Evaluation of expression in c++ pseudo code

[Joemeister]

I am trying to transform a infix mathematical expression into a postfix expression using the shunting yard algortihm but can only get so far by writing the pseudo code because I know exactly what to do through logical thinking but can't write the code that will help me do it. If you can have a look at the code I wrote and help me in writing the code, I will really appreciate it.

Same with evaluating/calculating that postFix that was transformed. I also wrote the pseudo code for that function with the hope that someone will be able to help me.

This is my pseodo code:

Shunting Yard:

string shuntingYard(string expression)
{

    string postFix = "";    //An initially empty array
    int ops[];              //Array ops
    int i = -1;             //This will be an index into the array ops

    while(/*tokens must still be read*/){

        //Read next token from the expression

        if(/*if the token is a constant or a variable*/)
        {
            //Append the token to the back of the postFix string
        }
        else if(/*the token is a function*/)
        {
            if(i == -1)
            {
                ++i;
                ops[i] = token;
            }
        }
        else if(/*the token ia a operator*/)
        {
            if(i == -1)
            {
                ++i;
                ops[i] = token;
            }
            else
            {
                while(/*i > -1 && ops[i] is an operator && token is left-associative && its precedence <= to that of the operator at ops[i] or the token's precedence is < that of the operator at ops[i]*/)
                {
                    //append ops[i] to the back of the postFix string;
                    --i;
                }
                if(i == -1)
                {
                    ++i;
                }
                ops[i] = token;     //Place the operator at index i in ops
            }
        }
        else if(/*token is a left-parenthesis*/)
        {
            if(i == -1)
            {
                ++i;
            }
            //place the token at ops[i];
        }
        else    //The token must be a right parenthesis
        {
            while(/*ops[i] is NOT a left parenthesis*/)
            {
                //append ops[i] to the back of the postFix string
                --i;
            }
            //ops[i] at this point should be a left parenthesis
            --i;
            if(/*ops[i] is a function, append it to the postFix string*/)
            {
                --i;
            }
        }
    }
    while(i > -1)
    {
        //append ops[i] to the back of the postFix string;
        --i;
    }
    //return the postFix string;
}

and this is the evaluation/calculation of the postfix expression:

int evaluate(string expr)
{

    int operands[];
    int i = -1;

    while(/*expr still has tokens to read*/)
    {
        /*token = next token from expr;*/
        if(/*If token is an integer or a variable*/){
            operands[++i] = token;
        }
        else
        {
            if(/*Token is a binary operator*/)
            {
                //Retrieve the elements from the operands at indices i and i-1;

                //Apply the operator to these operands;

                //Place the answer at operands[i-1];

                --i;
            }
            else    //The token is a unary operator
            {
                //Retrieve the element at index i from operands;

                //Apply the unary operator to this element;

                //Place the answer at operands[i];
            }
        }
    }
    //The answer for the expression will be at operands[0];
}

Thank you very very much!

:)

[L7Sqr]

I wrote a code snippet (in C++) not too long ago for doing just this. You can find it here

[Joemeister]

Awesome code! Thank you!

My other problem now is in my main.cpp I have a string like this:

#include <iostream>
#include "Expression.h"

using namespace std;


int main()
{
    /*
    Creating Expression objects.  Notice that all operators and 
    operands are seperated by spaces.  This will make it more 
    convenient to tokenize
    */

    Expression expr("x + y + sqrt 25 - 3");

    expr.instantiateVariable('x',5);//Set x = 5
    expr.instantiateVariable('y',3);//Set y = 3

    /*
    The output of the following statement should be:

    Answer: 10
    */

    cout<<"Answer: "<<expr.evaluate()<<endl;

}

How can I first instantiate the x and y before parsing the string?

[L7Sqr]

Without seeing the Expression class I'd assume to construct the following:

class Expression {
   std::map< std::sring, double > symtab_;
   // ...
public:
   double instantiateVariable (const std::string &var, double val) {
      std::map< std::string, double >::iterator sti = symtab_.find (var);
      if (sti == symtab_.end ()) {
         // raise an exception; create the variable; handle somehow
      }
      double old = *sti;
      *sti = val;
      return old;
   }
   // ...
};

That way, when you are parsing, you can keep track of the variables you've encountered along the way and assign them values later on.

One thing you may want to consider is what is a good default value (or if you should have one at all). In other words, if I provide x + y - 10 as the expression but only assign a value to y what should happen?

[Joemeister]

Oh yeah sorry about that!

Here is my class and it's members.

#ifndef EXPRESSION_H
#define EXPRESSION_H

#include <string>
#include <iostream>

using namespace std;

class Expression
{
    private:
        //...;
    public:
        /*The constructor receives a string expression in infix notation*/
        Expression(string);
        /*The destructor*/
        ~Expression();


        //GIVE THE VARIABLES VALUES
        void instantiateVariable(char, int);




        /*Evaluates and returns the answer to the expression*/
        int evaluate(string);

        // Function to convert Infix expression to postfix
        string shuntingYard(string);

        // Function to verify whether an operator has higher precedence over other
        int higherPrecedence(char, char);

        // Function to verify whether a character is operator symbol or not.
        bool IsOperator(char);

        // Function to verify whether a character is alphanumeric character (letter or numeric digit) or not.
        bool IsOperand(char);
};

[L7Sqr]

That is just the interface you are exposing. My comment was more to the point of not knowing what you had already implemented.

Regardless, you can use the symbol table idea I provided above to manage the expression internals (variables, values, etc.).

As I mentioned in your other post, propagating the expression as a string is a bad idea; it leads to having to do everything as a string. You've already discovered that is going to be messy.

If you look at the code snippet I provided the expression is converted to a stack of tokens internally. This is a very natural way to handle the RPN expression form. You would only need to extend that to consider something other than operators and numbers (that is where the symbol table comes in).

[Joemeister]

Currently, in your program. The infix does not contain any variables for ex.

x * (2 + 3)

and it only uses digits. How can I instantiate the variables in the expression (with a function) - giving the x, for example a value. AND then continue with the "new" infix, where the values are added?

[iamthwee]

Couldn't you just substitute the variables for numbers before you do anything?

Surely it would be a simple string replace.