-
stacks postfix aww fooey
Hello all I'm having a horrible time with this concept of stacks using postfix and prefix operators. I've looked all over for some sort of example showing me how to implement this idea and I can't find it anywhere. My professor says that you can use a cin.get(c) operation to utilize this type of operation. The whole idea has me totally bamboozled. So with that being said I beseech you all here in cprogamming.com could somebody anybody just show me a basic example of how this is done using cin.get(c).
-
Basic example:
Code:
#include <cctype>
#include <iostream>
using namespace std;
int main()
{
char stack[50];
char c;
int top = 0;
while ( cin.get ( c ) && c != '\n' ) {
if ( isspace ( c ) )
continue;
switch ( c ) {
case '+':
if ( top != 0 )
cout.put ( stack[--top] );
stack[top++] = c;
break;
case '-':
if ( top != 0 )
cout.put ( stack[--top] );
stack[top++] = c;
break;
default:
cout.put ( c );
break;
}
}
while ( top != 0 )
cout.put ( stack[--top] );
cout<<endl;
}
-
very nice
Now that wuz pretty cool. So if I wanted to implement someting for "parentheses" all I need is another switch statement
-
>So if I wanted to implement someting for "parentheses" all I need is another switch statement
Well, yes, but that's not all you need. You also need to work out precedence where parentheses are the highest precedence. That way the postfix expression is correct. The algorithm would go something like this:
Code:
#include <cctype>
#include <iostream>
using namespace std;
int precedence ( char c )
{
if ( c == '+' || c == '-' )
return 0;
else if ( c == '*' || c == '/' )
return 1;
else if ( c == '(' || c == ')' )
return 2;
return -1;
}
int main()
{
char stack[50];
char c;
int top = 0;
while ( cin.get ( c ) && c != '\n' ) {
if ( isspace ( c ) )
continue;
if ( precedence ( c ) != -1 ) {
if ( top != 0 ) {
if ( c == ')' ) {
while ( top != 0 && stack[top - 1] != '(' )
cout.put ( stack[--top] );
--top;
continue;
}
else {
while ( top != 0 && precedence ( stack[top - 1] ) >= precedence ( c ) ) {
if ( stack[top - 1] == '(' )
break;
else
cout.put ( stack[--top] );
}
}
}
stack[top++] = c;
}
else
cout.put ( c );
}
while ( top != 0 )
cout.put ( stack[--top] );
cout<<endl;
}
The code is pretty fugly (in other words, plagiarizing it will get you a bad grade ;)), but I'm too busy with other things to clean it up nice and pretty.