1. Infix to postfix Q

Hey everyone!
I'm looking for an algoritem which converts an infix squence to postfix. My problem is that I don't know what to do with the brackets in the squence. Here's what I have so far...

counter=0
init(stack)
While not end of line
if x is a number
print x
counter++
push(stack,x)
if counter==2
y=pop(stack)
print y
counter=0
while not_empty(stack)
y=pop(stack)
print y

I believe this would work if converted into code. How do I make it work if the expression contains brackets? i dont want the output to have any brackets in it

I would appreciate any help you could offer, and no code is needed (just an algoritem).

Thanks

2. Re:correction

Code:
```counter=0
init(stack)
While not end of line
if x is a number
print x
counter++
push(stack,x)
if counter==2
y=pop(stack)
print y
counter=0
while not_empty(stack)
y=pop(stack)
print y```
You can suggest your own idea of course.....

Code tagged by Hammer

3. sorry...

Take 3.. it won't let me post spaces for some reason

BEGIN
counter=0
init(stack)
While not end of line
if x is a number
{print x
counter++}
{push(stack,x)}
if counter==2
{y=pop(stack)
print y
counter=0}
}
while not_empty(stack)
{y=pop(stack)
print y}
END

I hope it's clearer now....

I can't be bothered to remove these posts, just read this before posting. Hammer

4. Do you mean like RPN (reverse polish notation)?

i.e.
2 + (3*4) equals
2 3 4 * +

If that's what you mean, I can help you. My parser uses RPN internally to speed things up.

AND:
Remove your two extra posts and edit your first message using [code] at the beginning and [/code] at the end.

5. Put you text in CODE tags to get the spaces right.

You know when you came here there was something at the top that said somehting along the lines of "Posting code? Please dear god read this first so the moderators don't pitch a fit".

You would have learned the glory of CODE tags.

Put this [CÖDE] before your code and this [/CÖDE] after it. (Use regular 'O's)

6. RPN == postfix

7. Originally posted by Sang-drax
Do you mean like RPN (reverse polish notation)?

i.e.
2 + (3*4) equals
2 3 4 * +

If that's what you mean, I can help you. My parser uses RPN internally to speed things up.

AND:
Remove your two extra posts and edit your first message using [code] at the beginning and [/code] at the end.
Yeah, that is what I mean, I would really appreciate if u can help.

I tried to edit/delete my posts but I get an "invalid username or pw" message. It's strange cause it doesn't give me any problems with signing in to post. I'm sorry for messing up, it won't happen again.

8. Hmm, I'll try to explain the algorithm I use. It works perfectly.

First, define every operator that is going to be used and assign each operator a predecence. Remember that ( and ) also are operators and they should have the highest predecence.

You'll also need a Token class, a token can contain a number or an operator (and functions and identifiers for more advanced parsers). A token class may look like this:
Code:
```struct Token()
{
enum {TypeOperator,TypeNumber,TypeExpression} Type;
double num;
char op;

queue<Token*> expression;
};```
The expression member is explained later.

I'll use this string as an example: "2*(5+6)^2"

The first task is to convert a string to a std::vector<Token>. I won't explain how this is done here, but it's not that hard using istream.

When the token vector is ready, the vector will look like this:
[ 2 * ( 5 + 6 ) ^ 2 ] size = 9
It is entirally made up by Tokens of TypeNumber and TypeOperator.

Now the real parsing begins, we will scan the vector for operator, processing the operator with the highest predecence first. Parenthesis is parsed using recursion.
Pseudo-code:
Code:
```queue<Token> MakeRPNExpression(vector<Token> tvector)
{

for predecence = highest to lowest
for index = 0 to size(tvector)
if tvector[index].Type == TypeOperator and
get_predecence(tvector[index].op) == predecence
{
//Process this operator

//Is it parenthesis?
if  vector[index].op == ')'
{
//collect every token within the parenthesis
//remeber to consider nested parenthesis!
//call recursivly
queue<Token> newtkns = MakeRPNExpression(subtokens);
//erase the tokens in the parenthesis
//insert a token with the queue
Token inserttkn(newtkns);
tvector.insert( curr_pos, inserttkn);
}

//Another binary operator
else
{
//get operands
Token left = offset-1;
Token right = offset+1;

queue<Token> new_expr;
//push operands
new_expr.push(left);
new_expr.push(right);
//push operator last
new_expr.push(op);

//Replace the operator and operands
//with a single expression token using
//container functions
}
}

//If everything went OK, the vector
//should now contain only one token
//with the expression in it.
return tvector[0].expression;
}```
Very esoteric, I know, but I'll show how it works using my example vector.
The vector now looks like this:
{2} {*} {(} {5} {+} {6} {)} {^} {2}

First, the parentheis is found, the tokens inside is converted resursivly to this: { {5} {6} {+} }, which is returned.

After replacement, the vector looks like this:
{2} {*} { {5} {6} {+} } {^} {2}
Note that the nested {} counts as a single token.

The next operator found is ^, the operands and operator are rearranged and after replacement and merging of the queues the vetor looks like this:
{2} {*}

The last operator found is *, the same procedure is followed and the final vector (only one token now) is:
{ {2} {5} {6} {+} {2} {^} {*} }
And we're done.

2*(5+6)^2 is
2 5 6 + 2 ^ * in RPN

I'll attach some real code from my parser, however I don't think it will help much. It is more generic, using a DataType class instead of number, and features binary and tertiary ooperators.
This typedef is used:
Code:
`typedef std::queue<Petter::Token> Expression;`
I think this is my longesy post in this forum, but also the hardest to understand, but I'm not a teacher, sorry.

9. This algorithm works with nested () as well as complex expressions:

3+(2+(3-5))*8+((23+6)*15)+5
equals in RPN:
3 2 3 5 - + 8 * + 23 6 + 15 * + 5 +