Infix to PostFix and Prefix (The Begining...)

zatora · #1 03-Dec-2008, 15:40

Hi all. My final project is about conerting from infix to post and to prefix according to the user selection.
This question will treat the infix to postfix
part, I need to understand how to convert an expression from infix to postfix so i can find the algorithm, but i don't know how to do the convertion.
I am also trying to use the stack built in class:

CPP / C++ / C Code:

 class stack<char>stk;
stk.push('A');
cout<<stk.top();// this line generates an error message
stk.pop();

i am wondering why i have this error (no operator found that takes<<...);
Thanks all.

davekw7x · #2 03-Dec-2008, 18:11

Quote:

Originally Posted by zatora

...I need to understand how to convert an expression from infix to postfix

So: If it isn't covered in your text or class notes or other class reference materials, find some examples and explanation. The first hit on google gave me http://scriptasylum.com/tutorials/in...tfix/index.htm

If that isn't adequate to meet your needs, look for others. If you have a specific question, I suggest that you post some code and tell us what you don't understand. My feeling is that the best use of this board is to try to get answers to specific questions. The more specific the question, the greater chance of a helpful response (usually).

Quote:

Originally Posted by zatora

I am also trying to use the stack built in class:

CPP / C++ / C Code:

 class stack<char>stk;

This makes the compiler think that you are going to create a whole new class named stack. (And, of course you haven't created any implementation.)

What you really want is to create an object of that the STL class:

CPP / C++ / C Code:

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack <char> stk;
    stk.push('A');
    cout << "After push, stk.size() = " << stk.size() 
         << " and stk.top() = '" << stk.top() << "'" << endl;
    stk.pop();
    cout << "After pop,  stk.size() = " << stk.size()  << endl;
    return 0;
}

Output:

Code:

After push, stk.size() = 1 and stk.top() = 'A'
After pop,  stk.size() = 0

Regards,

Dave

zatora · #3 04-Dec-2008, 00:41

thnaks Dave, i already looked into that page. It seems that i am stuck in how to do this using stack so i am trying to scan the infix (string) input create a dynamic array(string * postfix) then allocate it to the size of infix.length();
then i am not able to come up with anything it is like my brain is frozen.
so may be a couple of lines will help( i have to use stack). thanks forward

davekw7x · #4 04-Dec-2008, 09:21

Quote:

Originally Posted by zatora

...i already looked... i am stuck in how to do this using stack so i am trying to scan the infix (string) input create a dynamic array(string * postfix) then allocate it to the size of infix.length();...

That page just looks at the input string a character at a time (operands are single alphabetic characters; operators are single characters like '+', '*'). It tells you what to do at each step: If it's an operand, just append it to an output string; if its an operator, either push it on the stack or append it to the output string, depending on the state of the stack and the precedence of the operator relative to the top of the stack. If you are going to use the STL stack class, no allocation is needed by the user program. If the output string is a std::string object, no allocation is needed by the user program. See Footnote.

Now, if your operands are not single alphabetic characters, a little more work may be needed to parse them out.

For example: what if the program is supposed to handle operands that are C-Language style identifiers as well as numeric constants? Maybe it's a lot more work.

But you didn't actually tell us what the program requirements are. My personal methodology is to specify exactly what a program is supposed to do before I start writing code...

So: I hate to repeat myself, but

Quote:

Originally Posted by davekw7x

My feeling is that the best use of this board is to try to get answers to specific questions. The more specific the question, the greater chance of a helpful response (usually).

Regards,

Dave

Footnote:
If that page didn't help you, what else did you look at? How about this one: Infix to postfix conversion algorithm

Now, this example uses some special classes (apstring and apclass), which some denizens of the educational community decided (for some godawful reason) would be better for teaching than sticking with the C++ standard library and STL classes. I don't get it, but...

This example does show how to use a stack for the operators in the conversion. I do not (that's not) recommend that you use the special apxxx classes, but you can use the code to see what can be done for a simple problem.

The example assumes that operands are single upper-case alpha characters and operators are '*', '/', '+', '-', with the usual precedence. Parentheses are handled so, with a suitable main() function some runs could look like:

Code:

Enter an infix expression: A+B*C
Input : <A+B*C>
Output: <ABC*+>

Enter an infix expression: A*B+C
Input : <A*B+C>
Output: <AB*C+>

Enter an infix expression: A*(B+C)
Input : <A*(B+C)>
Output: <ABC+*>

Note that a "serious" program should have some industrial-grade error checking and handling, but this example might get you started.

If you don't like this one, then look for some others.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
inFix -->PostFix and Prefix Algorithm	zatora	C++ Forum	4	23-Nov-2008 16:07
C calculator	proximo	C Programming Language	5	09-Apr-2005 10:27

Infix to PostFix and Prefix (The Begining...)

Re: Infix to PostFix and Prefix (The Begining...)

Re: Infix to PostFix and Prefix (The Begining...)

Re: Infix to PostFix and Prefix (The Begining...)