Prev: string conversion (char[50] -> CString)
Next: Good windows C compiler linker
From: mitchellmomanyi on 15 Oct 2006 21:10
Hi. I am trying to write a program that would convert postfix
expressions to infix e.g ab* into (a*b) however I am having a problem
identifying and printing errors such as illegal characters. If anyone
can help I'd be greatful.This is my code so far:

#include<string>
#include<iostream>
#include "stackVector.h"
#include <cctype>

using namespace std;

Stack<string> postfix_to_infix();
void print(Stack<string> s1);
Stack<string> illegal_character(Stack<string> s2, string infix);

int main()
{
Stack<string> stack;
string value4;

stack = postfix_to_infix();
print(stack);
system("pause");
return EXIT_SUCCESS;
}

Stack<string> postfix_to_infix()
{
char value; Stack<string> stack,stack2; string
value1,value2,item,expression;

while(cin>>value)
{
if(isalpha(value)||value=='\0')
{
item=value;
stack.push(item);
}
else if(value=='~')
{
stack.pop(value1);
stack.push("(-"+value1+')');
expression=stack.top();
}
else
if((value=='/')||(value=='*')||(value=='+')||(value=='-')||(value=='%'))
{
stack.pop(value2);
stack.pop(value1);
stack.push('('+value1+value+value2+')');
expression=stack.top();
}
else
stack=illegal_character(stack,expression);
}
while(!stack.is_empty())
{
stack.pop(value1);
stack2.push(value1);
}
return stack2;
}

void print(Stack<string> s1)
{
string value;

while(!s1.is_empty())
{
s1.pop(value);
cout<<value<<endl;
}
}

Stack<string> illegal_character(Stack<string> s2,string infix)
{
string value;

while(s2.pop(value)&&value!="\0")
;
s2.push(value);
s2.push("An illegal character has been used in this expression");
cin.ignore(200, '\n');

return s2;
}

From: Ulrich Eckhardt on 16 Oct 2006 01:29
mitchellmomanyi(a)gmail.com wrote:
> I am trying to write a program that would convert postfix
> expressions to infix e.g ab* into (a*b) however I am having a problem
> identifying and printing errors such as illegal characters. If anyone
> can help I'd be greatful.

Okay, one thing up front: you are never telling what exactly your problems
are! So, how could anyone ever tell you how to fix them? Also, you are
talking about "illegal characters", but the definition of this term is
missing.

I'll try to give you some hints for things that struck me while reading the
code nonetheless...

> #include<string>
> #include<iostream>
> #include "stackVector.h"

What is that? Are you aware that the C++ standardlibrary has a stack<>
container wrapper?

> Stack<string> postfix_to_infix();
> void print(Stack<string> s1);
> Stack<string> illegal_character(Stack<string> s2, string infix);

Some notes here:
- You are passing several things by value that might be expensive to copy.
By default, I would pass any complex type by const reference.
- The print() function is pretty clear (though one might want to pass a
stream where to print it) but the other two aren't. What are their
parameters, their returnvalues and what are they supposed to do? This is
absolutely necessary in order to be able to code the functions correctly.

> Stack<string> stack;
> string value4;
>
> stack = postfix_to_infix();
> print(stack);

- 'value4' is unused. Try fiddling with the warning settings of your
compiler, many compilers can in fact warn you about unused variables.
- Prefer initialisation to assignment. In this case, you should have
written this instead:

Stack<string> stack = postfix_to_infix();

> system("pause");

This is non-portable. In general, I use something like this:

std::string dummy;
std::getline( std::cin, dummy);

...but that requires that you don't use std::cin for anything important in
the program.

> Stack<string> postfix_to_infix()
> {
> char value; Stack<string> stack,stack2; string
> value1,value2,item,expression;

Same problem as above. Declaring these here and in a single line just makes
it harder to see how they are used.

> while(cin>>value)
> {
> if(isalpha(value)||value=='\0')
> {
> item=value;
> stack.push(item);
> }
> else if(value=='~')
> {
> stack.pop(value1);
> stack.push("(-"+value1+')');
> expression=stack.top();
> }
> else if((value=='/')
> ||(value=='*')
> ||(value=='+')
> ||(value=='-')
> ||(value=='%'))
> {
> stack.pop(value2);
> stack.pop(value1);
> stack.push('('+value1+value+value2+')');
> expression=stack.top();
> }
> else
> stack=illegal_character(stack,expression);
> }

A few things here: splitting things in several functions would probably
help a bit. Also, while it is not very hard to understand, this is still
lacking a few comments. Now, the primary loop (as I understand it) just
takes a token and then branches on whether it is a
- variable name (isalpha())
- binary operator (+-*/%)
- unary operator (~)
What I don't understand is the special case for '\0', you might want to
comment that.
You could rewrite this a bit if you first created a function that returns a
single token (i.e. an operator or variable):

// read a single token
// Returns true if the token was successfully read.
bool read_token( std::istream& in, token& t);

'token' is defined as a structure like this:

struct token {
enum type_id { variable, unary_op, binary_op };

std::string value() const { return c; }
type_id type() const {
switch(c) {
case '~': return unary_op;
case '+': return binary_op;
case 'a':
case 'b': return variable;
default: throw std::runtime_error("invalid token");
}
}
private:
char c;
};

You can then write a loop like this:

std::list<token> tokens;
token t;
while( read_token( std::cin, t)) {
tokens.push_back(t);
}

In a second step (or, rather, a function), you can then reorder the tokens
from postfix to infix. In a third step, you can then print out the tokens,
adding brackets for readability.

Another question about the code you wrote is what the 'expression' variable
is supposed to do. The only place it is used is in illegal_character(),
otherwise it is only assigned the top of the stack. Why not call
illegal_character() with the top of the stack in the first place?

> while(!stack.is_empty())
> {
> stack.pop(value1);
> stack2.push(value1);
> }

IIUC, this just inverts the stack, right? If so, why not put it into its
own function? BTW: this piece of code places brackets different than the
rest...

HTH

Uli


--
FAQ: http://ma.rtij.nl/acllc-c++.FAQ.html
 | 
Pages: 1
Prev: string conversion (char[50] -> CString)
Next: Good windows C compiler linker