# infix to postfix expression string for evalution.

Discussion in 'C++' started by KidLogik, Feb 2, 2004.

1. ### KidLogikGuest

Hello!

I am converting an infix expression string into a postfix so that I
will be able to evaluate it easier ->

(5*(((9+8)*(4*6))+7)) == 598+46**7+*

I believe the rule is "Replace all occurances of two operands followed
by an operator by their infix equivalent"

This works fine like so ->

(2*2) == (22*)

but what happens if I need something bigger then 9?

(10*2) == (102*) ->

which would multiple the 0 and the 2 instead of 10*2...
Am I making any sense? Please help me.

Thanks.

KidLogik, Feb 2, 2004

2. ### John HarrisonGuest

"KidLogik" <> wrote in message
news:...
> Hello!
>
> I am converting an infix expression string into a postfix so that I
> will be able to evaluate it easier ->
>
> (5*(((9+8)*(4*6))+7)) == 598+46**7+*
>
> I believe the rule is "Replace all occurances of two operands followed
> by an operator by their infix equivalent"
>
> This works fine like so ->
>
> (2*2) == (22*)
>
> but what happens if I need something bigger then 9?
>
> (10*2) == (102*) ->
>
> which would multiple the 0 and the 2 instead of 10*2...
> Am I making any sense? Please help me.
>
> Thanks.

I think you need to add a space between the 10 and the 2.

John

John Harrison, Feb 2, 2004

3. ### Stewart GordonGuest

While it was 2/2/04 9:39 am throughout the UK, KidLogik sprinkled little
black dots on a white screen, and they fell thus:

> Hello!
>
> I am converting an infix expression string into a postfix so that I
> will be able to evaluate it easier ->

<snip>
> but what happens if I need something bigger then 9?
>
> (10*2) == (102*) ->

<snip>

Surely you should be building the postfixed expression in a binary form?
For example:

struct RPNNode {
enum { NUM, PLUS, MINUS, TIMES, DIVIDE } op;
int value;
};

That way, you won't have any such problem.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.

Stewart Gordon, Feb 2, 2004
4. ### David RubinGuest

KidLogik wrote:

> I am converting an infix expression string into a postfix so that I
> will be able to evaluate it easier ->

> (5*(((9+8)*(4*6))+7)) == 598+46**7+*

> I believe the rule is "Replace all occurances of two operands followed
> by an operator by their infix equivalent"

Firstly, there is more than one rule! When I wrote this program, I found
that dealing with parentheses and operator precedence was not
straightforward; it took a bit of fiddling around. In any case,
generally speaking, you need to use a stack and a parser...

[snip]
> but what happens if I need something bigger then 9?

> (10*2) == (102*) ->

> which would multiple the 0 and the 2 instead of 10*2...

The parser comes in handy for solving this problem. You can basically
parse the input string as characters using the following loop:

char *p = buf;
while(*p != '\n'){
if(isdigit((int)*p)){
/* operands */
}else
if(strchr("+-*/%^()", *p) == 0){
/* whitespace */
p++;
}else{
/* operators */
}
}

Note that my program does not evaluate the expression (which you seem to
imply as your goal), but rather converts between two strings: infix to
postfix.

HTH,

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

David Rubin, Feb 2, 2004
5. ### Thomas MatthewsGuest

David Rubin wrote:
> KidLogik wrote:
>
>
>>I am converting an infix expression string into a postfix so that I
>>will be able to evaluate it easier ->

>
>
>>(5*(((9+8)*(4*6))+7)) == 598+46**7+*

>
>
>>I believe the rule is "Replace all occurances of two operands followed
>>by an operator by their infix equivalent"

>
>
> Firstly, there is more than one rule! When I wrote this program, I found
> that dealing with parentheses and operator precedence was not
> straightforward; it took a bit of fiddling around. In any case,
> generally speaking, you need to use a stack and a parser...
>
> [snip]
>
>>but what happens if I need something bigger then 9?

>
>
>>(10*2) == (102*) ->

>
>
>>which would multiple the 0 and the 2 instead of 10*2...

>
>
> The parser comes in handy for solving this problem. You can basically
> parse the input string as characters using the following loop:
>
> char *p = buf;
> while(*p != '\n'){
> if(isdigit((int)*p)){
> /* operands */
> }else
> if(strchr("+-*/%^()", *p) == 0){
> /* whitespace */
> p++;
> }else{
> /* operators */
> }
> }
>
> Note that my program does not evaluate the expression (which you seem to
> imply as your goal), but rather converts between two strings: infix to
> postfix.
>
> HTH,
>
> /david
>

If one throws the operators and numbers into a binary tree, then
conversion is just a matter of how the tree is traversed. I wrote
the program so long ago, I don't remember how I handled the parens.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Thomas Matthews, Feb 2, 2004
6. ### David RubinGuest

Thomas Matthews wrote:

[snip - infix to postfix]
> > Firstly, there is more than one rule! When I wrote this program, I found
> > that dealing with parentheses and operator precedence was not
> > straightforward; it took a bit of fiddling around. In any case,
> > generally speaking, you need to use a stack and a parser...

[snip]
> If one throws the operators and numbers into a binary tree, then
> conversion is just a matter of how the tree is traversed. I wrote
> the program so long ago, I don't remember how I handled the parens.

I found the stack-based algorithm in the project notes from some random
college intro CS course on the web. I usually just browse college course
web pages when I'm looking for a short "keep your skills sharp" project.
The stack algorithm explicitly described how to handle parens, but it
was apparantly lacking a few details.

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

David Rubin, Feb 3, 2004

### Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.