infix to prefix.....damn my eyes are fried

This is a discussion on infix to prefix.....damn my eyes are fried within the C++ Programming forums, part of the General Programming Boards category; this program takes infix algebraic notations and converts them to prefix notations....i get too many operators though.... 2-3+4 ends up ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    719

    infix to prefix.....damn my eyes are fried

    this program takes infix algebraic notations and converts them to prefix notations....i get too many operators though....
    2-3+4 ends up looking lik
    --+234 //notice the extra - ...but not +

    if anyone's got some serious time to kill, could you look over this for me? you should be able to cut, paste, compile, run....at system prompt just type in different equations to see the output...type 'exit' to quit...oh yea, i forgot to include 'support' for exponents (2^3)


    btw.........i know stack<char> is not what i really want to use (the char part anyway), but it keeps this logical testing a little easier)

    Code:
    #include <iostream>
    #include <string>
    #include <stack>
    
    using namespace std;
    
    //i love macros
    #define isOp(x) (x=='-'||x=='+'||x=='/'||x=='*')
    #define isHigh(x) (x=='*'||x=='/')
    #define isLow(x)  (x=='-'||x=='+')
    #define isSame(x, y) ((isHigh(x) && isHigh(y)) ||(isLow(x) && isLow(y)))
    #define isClose(x) ((x==']')||(x==')')||(x=='}'))
    #define isOpen(x) ((x=='[')||(x=='(')||(x=='{'))
    
    string reverse(string s)
    {
        string tar;
        
        for(int i = s.size(); i >= 0; i--)
        {
            tar += s[i];        
        }        
        return tar;
    }    
    
    
    string infix2prefix(string source)
    {
        stack<char> output;    
        stack<char> ops;
        string eq(reverse(source));   //reverse equation
        char c;
    
        //for each element in equation
        for(int i = 0; i < eq.size(); i++)
        {
            c = eq[i];                           //prevent repeated dereferencing
    
            //if not /-+*[]{}()
            if((!isOp(c))&&(!isClose(c))&&(!isOpen(c)))
                    output.push(c);
    
            //if is )}]
            if(isClose(c))
                    ops.push(c);
            //if is /+-*^
            if(isOp(c))
            {
                     //if stack is empty put operator on stack
                    if(ops.empty())
                    {
                        ops.push(c);
                    }else{
                        //else if top of stack is )]or} push operator on stack
                        if(isClose(ops.top()))   
                        {
                            ops.push(c);
                        }    
                        //is precedence is the same or higher push it onto
                        //operator stack...else, push it straight to output 
                        //stack
                        if(isSame(c, ops.top())||isHigh(c))
                        {
                            ops.push(c);
                        }else{
                            output.push(c);
                        }        
                    }    
            }             
            
              //if ([or{                  
            if(isOpen(c))
            {
                 //move operator stack to output stack
                while(!ops.empty())
                {
                    output.push(ops.top());
                    ops.pop();
                }
            }        
                         
            
        }   
        //put remaining operators on output stack
        while(!ops.empty())
        {
            output.push(ops.top());
            ops.pop();
        }    
                
        //turn output stack into a string
        eq = ""; 
        while(!output.empty())
        {
                eq += output.top();
                output.pop();
        }    
        return eq;
    }   
    
    
    int main()
    {
    	
    	string eq;
    	
    	char c;
    	cin >> eq;
    	while(eq != "exit")
    	{
    	    cout << infix2prefix(eq) << endl;	    
    	   	cin >> eq;
    	}
    	
    	return 0;
    }

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >if anyone's got some serious time to kill, could you look over this for me?
    I (and others) have posted full implementations along with detailed explanation for this very problem.

    >//i love macros
    A few whacks with the clue-bat will fix that right up.

    >i get too many operators though
    Work out your logic on paper first, then step through your code and make sure that it does what you think it does. Debugging is an important part of programming, and being given the solution won't help you as much as sloughing your way through the process of finding it.
    My best code is written with the delete key.

  3. #3
    i dont know Vicious's Avatar
    Join Date
    May 2002
    Posts
    1,200
    >//i love macros
    A few whacks with the clue-bat will fix that right up.
    Macros are a bad thing??
    What is C++?

  4. #4
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    i have worked it out on paper....i just cannot find the damn thing and i've been staring at this screen for the past........wow....long long time.....

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Macros are a bad thing??
    Well...yes. In C they're a necessary evil, but in C++ you have inline functions and function tempates. There's no reason to use the error prone preprocessor when there are much better alternatives.
    My best code is written with the delete key.

  6. #6
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    This is not related to the actual problem, but could be useful.

    Right now, you have your operators and their predecence hard-coded into your application. To add an operator with another predecence would require a large amount of effort.

    To be a little more generic, try to create a list of operators and predecence at one place which is easy to change.

    Here's one idea:
    Code:
    struct BinaryOperator {
      int predecence;
      std::string op;
      double (*func)(double,double);
    };
    
    operatorList.push_back(4, "*", multiply);
    operatorList.push_back(4, "/", divide);
    operatorList.push_back(2, "+", add);
    Back to the actual problem. You say you've worked it out on paper. Please show us.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >i just cannot find the damn thing
    Start with your reverse function. It has a fencepost error and also doesn't properly reverse parentheses. When the expression is ill-formed, the algorithm will bomb.
    My best code is written with the delete key.

  8. #8
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    sang-
    i actually did change my code to look something like you posted....well, nothing like it,
    but the same concept....and made a small class to help deal with operators.... overloaded < and > to compare precedence......

    prelude-
    thanks for pointing out the ())( thing.....i would have never seen that.....i assumed that was a pretty cut and dry algorithm.....what is a fencepost error?

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >i assumed that was a pretty cut and dry algorithm
    Those are the ones we screw up most frequently.

    >what is a fencepost error?
    An error where your logic is off by one. In the following loop:
    Code:
    for(int i = s.size(); i >= 0; i--)
    s.size() is out of bounds for the array, it should be s.size() - 1.
    My best code is written with the delete key.

  10. #10
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    thanks again for pointing that out.....

    i'll let you know how much adding -1 helps me figure it out (if not solve it, which i doubt)....
    for now, i'm done with this....too much thinking and reading.... i've certainly spent the greater portion of the last 12 hours at my computer working on some sort of code....i just can't take anymore

  11. #11
    Registered User
    Join Date
    Oct 2004
    Posts
    19
    Misplaced curious to know how you decided between pre and postfix?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM

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