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