Thread: 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;
}

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.....

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?

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

Misplaced curious to know how you decided between pre and postfix?