Shunting yard algorithm.

This is a discussion on Shunting yard algorithm. within the C++ Programming forums, part of the General Programming Boards category; I am trying to implement the shunting yard algorithm for a graphing calculator that I'd like to make. I've managed ...

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    71

    Shunting yard algorithm.

    I am trying to implement the shunting yard algorithm for a graphing calculator that I'd like to make. I've managed before to get it to solve basic equations that don't use braces, or trigonometric functions.

    Now, I'd like to get those working ^_^.

    I've taken a look at the pseudo code at:

    http://en.wikipedia.org/wiki/Shunting_yard_algorithm

    I'd like to do this algorithm with character arrays. Since, I am doing this with character arrays, the operations are going to be a bit different, and is what I am having troubles with.

    I was thinking that once I have all the function arguments read into my "stack" (character array), that I could just reverse all it's contents then it would look like a stack when "popping" off elements.

    ie:

    Stack (pushing elements)

    1,2,3,4,5,6,7,8,9

    [1][2][3][4][5][6][7][8][9]

    When you start popping them off you get:

    9,8,7,6,5,4,3,2,1

    (I think anyways...)

    I was also thinking I might be able to treat the character array backwards to simulate the stack.

    Anyways, I will post some of my sample code:

    Code:
    void Math::XInfix_Postfix(char* Inf)
    {
        // sort from infix to postfix (norm notation to RPN notation)
        int espot = 0;
        int esize = strlen(Inf);
        bool flag = false;
        int num = 0;
        int out = 0;
        int x = 0;
        int y = 0;
        
        char temp_token;
        
        
        delete [] Output;
        Output = new char[esize];
        
        // while there are tokens to be read:
        while(espot <= esize)
        {
            // if token is number
            if(isdigit(Inf[espot]))
            {
                // read in a token (funny part, because a token is more then 1 char)
                num = espot;
                while(isdigit(Inf[num]) || Inf[num] == '.')
                {
                    Output[out] = Inf[num];
                    num++;
                    out++;
                }
                out = 0;
                espot = num;
                num = 0;
            }
    
            else
            {
                // if its a function arguement (ie +,-,/,*,^)
                if(Inf[espot] == '+' || Inf[espot] == '-' || Inf[espot] == '*' ||
                   Inf[espot] == '^' || Inf[espot] == '/')
                {
                    temp_token = Inf[espot];
                    
                    /**** Need to get it shoved in BEDMAS format ****/
                    
                    switch( temp_token )
                    {
                        case '-':
                            x = y;
                            flag = false;
                            while( x <= strlen(Stack) )
                            {
                                if( Stack[x+1] == '(' )
                                {
                                    flag = true;
                                }
                                    
                                else if( Stack[x+1] == '*' || Stack[x+1] == '/' ||
                                    Stack[x+1] == '^' )
                                {
                                    temp_token = Stack[x];
                                    Stack[x-1] = Stack[x];
                                    Stack[x] = temp_token;
                                }
                                x++;
                            }
                        break;
                        
                        case '+':
                        break;
                        
                        case '/':
                        break;
                        
                        case '*':
                        break;
                        
                        case '^':
                        break;
                    }
    
                    out = 0;
                }
                
                // function arguement seperator( brackets )
                else
                {
                    out = strlen(Stack)+1;
                    x = strlen(Output);
                    Stack[out] = Inf[espot]; // put the seperator on stack
                    
                    //while topmost element of stack isn't a left paranthesis
                    //pop elements out to output.
                    while(num < out)
                    {
                        if(Stack[num] != '(')
                        {
                            Output[x] = Stack[num];
                            Output[x+1] = ' ';
                        }
                        else
                        {
                            y = 0;
                            while(num < out)
                            {
                                Stack[y] = Stack[num];
                                num++;
                            }
                            
                            break;
                        }
                        
                        y++;
                        x += 2;
                        num++;
                    }
                }
                
            }
            
            espot++;
            
        }
            
        cout << Stack;
        
        return;
    }
    I know something is definately messed up when I start trying to perform operations that are dependant on braces etc.

  2. #2
    Notorious Turbo C killer blacksnake's Avatar
    Join Date
    Jan 2007
    Location
    philippines
    Posts
    50

    Question

    by the way, do you have push and pop function to get the right algorithm?
    Turbo C Makes me Sick....i just want to learn data structures in latest c++

    Le Tormente (fr. the torment)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. More help needed w/ Shunting Yard Algorithm
    By P4R4N01D in forum C Programming
    Replies: 3
    Last Post: 12-02-2008, 04:13 PM
  2. Shunting Yard Algorithm
    By EvilGuru in forum C Programming
    Replies: 3
    Last Post: 11-04-2005, 12:20 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21