Archived

This topic is now archived and is closed to further replies.

Gammastrahler

Infix to Postfix conversion

Recommended Posts

hi i have written a calculator that first converts from infix to postfix. generally it works, but the problem is that if my infix calculations are too complicated, the conversion no longer works. for this expression (3+2)+1+3*((4*4+6)/2+3)*8+(5+4)/(3+1), my program prints out -62, whereas C++ and the Windows calculator print out -190. here is my source code for the conversion:
  

int precedence(char op)
{
  if (op == ''+'' ) return 0;
  if (op == ''-'') return 0;
  if (op == ''*'' ) return 1; 
  if (op == ''/'') return 1;
}

void infixToPostfix()
{
  char str[255] = "(3-2)+1-3*((4*4+6)/2-3)*8+(5-4)/(3-1)";
  char ch;
  stack<char>	st;
  char op;
  int n = 0;

  while ((ch = str[n++]) != ''\0'')
  {
    if (isdigit(ch))
      postfix[x++] = ch;
 
    if ( ch == ''('' )
    st.push(ch);
  else if (ch == '')'')
  {
    char op = st.pop();
    while ( op != ''('' )
    {
     if (op != ''('') postfix[x++] = op;
     if (!st.count()) break;
     op = st.pop();
    }
   }
  else if ( ch == ''+'' || ch == ''-'' || ch == ''*'' || ch == ''/'' )
  {
    while (st.count() && ( precedence(st.top()) >= precedence(ch) ))
    {
      char op = st.pop(); 
      if (op != ''('')
        postfix[x++] = op;
    }
    st.push(ch);
    }
  }
  while ( st.count() )
  {
    op = st.pop();
    if (op != ''('')  postfix[x++] = op;
  }
  postfix[x++] = ''\0'';
}
  
And here is the source code for my expression evaluation:
  
int main()
{
	printf("%d\n", (3-2)+1-3*((4*4+6)/2-3)*8+(5-4)/(3-1));
	stack<int>	expr;
	int n = 0;
	char ch;

	infixToPostfix();

	printf(postfix);

	while ((ch = postfix[n++]) != ''\0'')
	{
		if (isdigit(ch))
			expr.push(ch - ''0'');
		if (ch == ''+'' )
			expr.push(expr.pop() + expr.pop());
		if (ch == ''*'' )
			expr.push(expr.pop() * expr.pop());
		if (ch == ''-'' )
		{	
			int a = expr.pop();
			expr.push(expr.pop() - a);
		}
		if (ch == ''/'' )
		{
			int a = expr.pop();
			expr.push(expr.pop() / a);
		}
	}

	printf("\n");

	printf("Ergebnis: %d\n", expr.pop());

	return 0;
}

can someone help me on this problem?

thanks
Gammastrahler

  

Share this post


Link to post
Share on other sites
Haven't wrapped my brain completely around your algorithm, but this part of the code:


else if ( ch == '+' || ch == '-' || ch == '*' || ch == '/' )
{
while (st.count() && ( precedence(st.top()) >= precedence(ch) ))
{
char op = st.pop();
if (op != '(')
postfix[x++] = op;
}
st.push(ch);
}


Shouldn't there be an else clause on the if (op != '(')
I would think you'd want that '(' pushed back on the stack, and break out of the while loop.

[edited by - jediknight219 on October 22, 2002 10:58:15 AM]

Share this post


Link to post
Share on other sites