How to convert Infix notation to postfix notation

i have a string as (a+b)+8-(c/d) in Infix form.

how can i convert it to postfix form using C language,,,????

Tameem

On Oct 26, 12:33*pm, Tameem <etam...@gmail.com> wrote:
> i have a string as (a+b)+8-(c/d) in Infix form.
>
> how can i convert it to postfix form using C language,,,????

I will assume that that string is not the ONLY string you have to
convert. If it is, then the answer is

int main()
{
printf("ab+8+cd/-\n");
}

Each one of the following productions should be written as a separate
C function.

expression -> additionFactor [ "+"|"-" expression ]
additionFactor -> multiplicationFactor [ "*"|"/" expression ]
multiplicationFactor -> term
term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance

Write code using the above "productions" that emits postfix code. For
each production write one C function. I won't write C for you because
I don't like C, I suck at it through disuse consequent on my dislike,
and it's your homework assignment, not mine.

"->" means "consists of the following material left to right"

"|" means "or"

Lower case and camelCase words are grammar categories that will
correspond to procedures in YOUR code

Upper case words are lexemes recognised by C code

Quoted material occurs as is.

Material in square brackets is optional. An expression could be just
an additionFactor. In turn an additionFactor can be just a
multiplicationFactor and a multiplication factor a number. Therefore,
"3" is an expression.

When you parse a "term" as "(" expression ")" you must look ahead in
the overall algorithm I shall give you to find, not the first right
parenthesis, but the one that actually balances the left parenthesis.
To do this, maintain a counter. Increment it by one for each left
parenthesis the lookahead sees: decrement it by one for each right
parenthesis. When you see right parenthesis and the counter goes to
zero, you have found the right parenthesis.

OK, here's the untested and uncompiled C Sharp like pseudo code for
"expression": convert it to C:

string expressionMain(string strInstring)
{
int intIndex1 = 0;
string strPolish = "";
return expression(strInstring, ref intIndex1, ref strPolish);
}
string expression(string strInstring, ref int intIndex1, ref string
strPolish)
{
if (!additionFactor(string strInstring,
ref intIndex1,
ref strPolish)) return "Not valid";
if (strInstring[intIndex]=='+' || strInstring[intIndex]=='-')
{
int intIndexSave = intIndex1; intIndex1++;
if (expression(strInstring, ref intIndex1, ref strPolish))
strPolish += strInstring[intIndexSave];
else return("Not valid");
}
return strPolish;
}

C Sharp idioms: ref followed by type in a formal parameter list in a
function decl is like using asterisk in front of a parameter in C. It
means that the parameter is passed by reference. In C Sharp, a very
cool language, you must ALWAYS use the keyword ref in the "actual
parameters" passed when you call the function just so you know what
the hell you are doing, as opposed to C which likes to fool you.

Chapter 3 of my book Build Your Own .Net and Compiler (Edward G.
Nilges, Apress May 2004) provides a complete solution for this
homework but in Visual Basic .Net. Therefore this is not a commercial
promotion. If you find my book useful, buy it, check it out of the
library, or steal it.

spinoza1111

Tameem wrote:

> i have a string as (a+b)+8-(c/d) in Infix form.
>
> how can i convert it to postfix form using C language,,,????

This has very little to do with the /language/ C, i.e., there's
no "built-in" way to accomplish this conversion. However, it's
of course possible to implement such a converter in C, e.g., by
writing a recursive-descent parser (for a good deal of details,
see <http://en.wikipedia.org/wiki/Operator-precedence_parser>).

You might also want to take a look at the GNU assembler (gas,
which is part of the GNU binutils package), which implements
such a recursive-descent parser to evaluate constant expressions.


mike

Michael Schumacher

On Oct 26, 12:33*am, Tameem <etam...@gmail.com> wrote:
> i have a string as (a+b)+8-(c/d) in Infix form.
>
> how can i convert it to postfix form using C language,,,????

It this homework?

Gene

spinoza1111 <> writes:

> On Oct 26, 12:33Â*pm, Tameem <etam...@gmail.com> wrote:
>> i have a string as (a+b)+8-(c/d) in Infix form.
>>
>> how can i convert it to postfix form using C language,,,????
>
> I will assume that that string is not the ONLY string you have to
> convert. If it is, then the answer is
>
> int main()
> {
> printf("ab+8+cd/-\n");
> }
>
> Each one of the following productions should be written as a separate
> C function.
>
> expression -> additionFactor [ "+"|"-" expression ]
> additionFactor -> multiplicationFactor [ "*"|"/" expression ]
> multiplicationFactor -> term
> term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance

This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

> Write code using the above "productions" that emits postfix code.

To the OP: please don't; Spinoza1111 is leading you astray. Post in a
group about programming (comp.programming is a good one) for better
advice on how to go about this. Also, if this is homework/coursework,
be open about that and explain how far you have been able to get on
your own.

<snip off-topic C#>
--
Ben.

Ben Bacarisse

On Oct 26, 8:20*pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> spinoza1111<spinoza1...@yahoo.com> writes:
> > On Oct 26, 12:33*pm, Tameem <etam...@gmail.com> wrote:
> >> i have a string as (a+b)+8-(c/d) in Infix form.
>
> >> how can i convert it to postfix form using C language,,,????
>
> > I will assume that that string is not the ONLY string you have to
> > convert. If it is, then the answer is
>
> > int main()
> > {
> > printf("ab+8+cd/-\n");
> > }
>
> > Each one of the following productions should be written as a separate
> > C function.
>
> > expression -> additionFactor [ "+"|"-" expression ]
> > additionFactor -> multiplicationFactor [ "*"|"/" expression ]
> > multiplicationFactor -> term
> > term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance
>
> This is not the usual grammar for expressions and is poor advice for
> someone learning this stuff.
>
> > Write code using the above "productions" that emits postfix code.
>
> To the OP: please don't;Spinoza1111is leading you astray. *Post in a

Ben, please indicate the errors and don't imitate Seebach by
discussing personalities instead of ideas. As it is, you sound like a
fundamentalist *imam*.

> group about programming (comp.programming is a good one) for better
> advice on how to go about this. *Also, if this is homework/coursework,
> be open about that and explain how far you have been able to get on
> your own.
>
> <snip off-topic C#>
> --
> Ben.- Hide quoted text -
>
> - Show quoted text -

spinoza1111

On Oct 26, 8:20*pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> spinoza1111<spinoza1...@yahoo.com> writes:
> > On Oct 26, 12:33*pm, Tameem <etam...@gmail.com> wrote:
> >> i have a string as (a+b)+8-(c/d) in Infix form.
>
> >> how can i convert it to postfix form using C language,,,????
>
> > I will assume that that string is not the ONLY string you have to
> > convert. If it is, then the answer is
>
> > int main()
> > {
> > printf("ab+8+cd/-\n");
> > }
>
> > Each one of the following productions should be written as a separate
> > C function.
>
> > expression -> additionFactor [ "+"|"-" expression ]
> > additionFactor -> multiplicationFactor [ "*"|"/" expression ]
> > multiplicationFactor -> term
> > term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance
>
> This is not the usual grammar for expressions and is poor advice for
> someone learning this stuff.
>
> > Write code using the above "productions" that emits postfix code.
>
> To the OP: please don't;Spinoza1111is leading you astray. *Post in a

I would have thought given your technical capabilities that you would
be able, instead of engaging in Fox news style politics of personal
destruction, to identify all flaws in my approach, whether in the
formal grammar of C# pseudo code.

If you cannot, I need an apology from you. NOW, punk.

> group about programming (comp.programming is a good one) for better
> advice on how to go about this. *Also, if this is homework/coursework,
> be open about that and explain how far you have been able to get on
> your own.
>
> <snip off-topic C#>

C# is what C should be. As I indicated, C Sharp was used as pseudocode
because it is probably a homework assignment and the OP needs to do
this homework. The OP probably received poor algorithm guidance from
the teacher, especially if the teacher was like most people here.
> --
> Ben.- Hide quoted text -
>
> - Show quoted text -

spinoza1111

spinoza1111 <> writes:

> On Oct 26, 8:20Â*pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> spinoza1111<spinoza1...@yahoo.com> writes:
<snip>
>> > expression -> additionFactor [ "+"|"-" expression ]
>> > additionFactor -> multiplicationFactor [ "*"|"/" expression ]
>> > multiplicationFactor -> term
>> > term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance
>>
>> This is not the usual grammar for expressions and is poor advice for
>> someone learning this stuff.
>>
>> > Write code using the above "productions" that emits postfix code.
>>
>> To the OP: please don't;Spinoza1111is leading you astray. Â*Post in a

[The formatting errors in the above were added by you. My typing is
bad, but not /that/ bad.]

> I would have thought given your technical capabilities that you would
> be able, instead of engaging in Fox news style politics of personal
> destruction, to identify all flaws in my approach, whether in the
> formal grammar of C# pseudo code.

It's not topical here. There must be lots of groups where you can get
advice on writing a grammar for simple expressions, but I don't know,
off hand, where would be the best place. I suggested comp.programming
to the OP, but that is probably not the best place for your question.

> If you cannot, I need an apology from you. NOW, punk.

That's OK then.

<snip>
--
Ben.

Ben Bacarisse

On Oct 27, 11:15*am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> spinoza1111<spinoza1...@yahoo.com> writes:
> > On Oct 26, 8:20*pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> >>spinoza1111<spinoza1...@yahoo.com> writes:
> <snip>
> >> > expression -> additionFactor [ "+"|"-" expression ]
> >> > additionFactor -> multiplicationFactor [ "*"|"/" expression ]
> >> > multiplicationFactor -> term
> >> > term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance
>
> >> This is not the usual grammar for expressions and is poor advice for
> >> someone learning this stuff.

You have not shown that it is INCORRECT. It's possible that the
"usual" grammar is incorrect (as in the case of left recursion) given
Gresham's Law that 99% of everything is crap. You need to show that
the grammar is either actually incorrect or not suitable for manual
interpretation, and I do not, personally think you qualified to do so.
This takes experience in writing an actual parser by hand.

In the first production it is obvious that on return from
additionFactor(), the parser can advance the index, and check it for
greater than end. If the index is past the end, we're done. If it is
not, the parser can check either for a plus or a minus.

If either character occurs the parser then calls itself with a source
string that is necessarily smaller guaranteeing the safety of the
recursion. But, there must be an expression when there is an operator.

Disprove this informal logic and desist the Fox news crap, please.
>
> >> > Write code using the above "productions" that emits postfix code.
>
> >> To the OP: please don't;Spinoza1111is leading you astray. *Post in a
>
> [The formatting errors in the above were added by you. *My typing is
> bad, but not /that/ bad.]
>
> > I would have thought given your technical capabilities that you would
> > be able, instead of engaging in Fox news style politics of personal
> > destruction, to identify all flaws in my approach, whether in the
> > formal grammar of C# pseudo code.
>
> It's not topical here. *There must be lots of groups where you can get
> advice on writing a grammar for simple expressions, but I don't know,
> off hand, where would be the best place. *I suggested comp.programming
> to the OP, but that is probably not the best place for your question.

His goal is to write a C program, but we don't want to give him the
homework solution. It appears that his instructor in fact knows about
as much as you about writing a recursive descent parser by hand.
Therefore he's in the right place.
>
> > If you cannot, I need an apology from you. NOW, punk.
>
> That's OK then.
>
> <snip>
> --
> Ben.

spinoza1111

On Oct 25, 11:33*pm, Tameem <etam...@gmail.com> wrote:
> i have a string as (a+b)+8-(c/d) in Infix form.
>
> how can i convert it to postfix form using C language,,,????

As others have said, there's no C-specific way of doing this.
However, here are the general steps you'll need to take:

First, you will need to separate the string into distinct *tokens*.
In your example, you have four kinds of tokens -- operators
('+','-','*','/'), separators ('(',')'), constants ('8'), and
identifiers ('a','b','c','d'). Generally, you'll have a set of rules
that determines what characters make up a particular kind of token
(for example, an identifier must start with a letter and consist of
only letters and digits: "a1", "foo", "x", etc.). As you scan each
character, you'll check against the currently active rule and if it
matches, you'll add it to the token.

There are two ways to go on the next step. You can either build a
full-blown recursive descent parser (a decent explanation appears on
Wikipedia), or you can use a simple stack-based converter. For the
stack-based converter, as you read the expression, you'll pass
constants and identifiers straight to output, and you'll push and pop
operators on the stack based on their precedence. If the operator on
the top of the stack has a lower precedence than the current operator,
then push the current operator. If the operator on the stack has an
equal or higher precedence than the current operator, then pop the
operator off the stack and write it to output, then push the current
operator on the stack. lparens are always pushed onto the stack;
rparens cause everything on the stack to be popped to the next
lparen. Neither lparens nor rparens are written to output.

Given your example, the operations would look something like this:

1. Read '(', push it onto the stack. Stack contents = {'('}
2. Read 'a', write it to output. Output string = "a"
3. Read '+', push it on the stack: {'(', '+'}
4. Read 'b', write it to output: "a b"
5. Read ')', pop everything off the stack to the next '(', but don't
write '(' to output. Output string is "a b +", stack contents = {}
6. Read '+', push it onto the stack: {'+'}
7. Read '8', write it to output: "a b + 8"
8. Read '-', has same precedence as '+', so pop '+' from stack, write
it to output, and push '-': "a b + 8 +", {'-'}
9. Read '(', push it onto the stack: {'-', '('}
10. Read 'c', write it to output: "a b + 8 + c"
11. Read '/', push onto stack: {'-', '(', '/'}
12. Read 'd', write to output: "a b + 8 + c d"
13. Read ')', pop everything to '(': "a b + 8 + c d /", {'-'}
14. End of string, pop remainder of stack: "a b + 8 + c d / -"

John Bode