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.