Infix to Postfix expression

[Progesco]

This is algorithm to converts an ordinary infix arithmetic expression to a postfix expression ( such as (6+2)*5-8/4 to 62+5*8/4- )

while there are more characters in the input
{
Read next symbol ch in the given infix expression.
If ch is an operand put it on the output.
If ch is an operator i.e.* , /, +, -, or (
{
If stack is empty push ch onto stack;
Else check the item op at the top of the stack;
while (more items in the stack &&
priority(ch) <= priority (op) )
{
pop op and append it to the output, provided it
is not an open parenthesis
op = top element of stack
}
push ch onto stack
}
If ch is right parenthesis ‘)’
Pop items from stack until left parenthesis
reached
Pop left parenthesis and discard both left
and right parenthesis
}/* now no more characters in the infix expression*/
Pop remaining items in the stack to the output.

and here is my program

#include <iostream>
#include <conio.h>
#include <stack>
#include <string>
using namespace std;

int priority(char a) 
{
     int temp;
     if( a=='^')
         temp = 1;
     else
     {
         if(a=='*' || a=='/')
              temp = 2;
         else
         {
             if(a=='+' || a=='-')
                  temp = 3;
         }
     }
     return temp;
}
         
int main()
{
    string infix;
    cout << "Enter an arithmetic expression: " << endl;
    cin >> infix;
    
    stack<char> temp;
    stack<char> postfix;
    
    int i;
   
    for (i=0; i<11; i++)
    {
       if (infix[i]!='+' || infix[i]!='-' || infix[i]!='*' || infix[i]!='/' || infix[i]!='^' || infix[i]!='(' || infix[i]!=')')
          {postfix.push(infix[i]);
          cout << postfix.top();}
       else
       {
           if (infix[i]=='(')
              temp.push(infix[i]);
           else
           {
               if (infix[i]=='+' || infix[i]=='-' || infix[i]=='*' || infix[i]=='/' || infix[i]!='^')
               {
                    while (priority(temp.top()) <= priority(infix[i]))
                    {
                         postfix.push(infix[i]);
                         cout << postfix.top();
                         temp.pop();
                    }
                    temp.push(infix[i]);
               }
               else if(infix[i]==')')
               {
                    while (temp.top() != '(')
                    {
                         postfix.push(infix[i]);
                         cout << postfix.top();
                         temp.pop();
                    }
                    temp.pop();
               }
                   
           }
       }
    }      
       
    getch();
    return 0;
}

Please help me to find out where is my mistake :(

[R0mai]

There are some problems with your code :

Why do use a stack as your output?? Use a stringstream or at least a vector.

for (i=0; i<11; i++) Why 11? Shouldn't this be infix.lenght() ?

In your first long if statement you are using || instead of &&. Don't output to the console in the middle of the algorithm (unless you are debugging), put everything into the output container, and out put at the end if your program.

Notice that the if tree in main is just a simple if {} else if {} else if {} ... tree, it seems more complex because of your indentation. (same applies to priority()'s ifs)

If you rearrange the if, else blocks then your current first block

postfix.push(infix[i]);
cout << postfix.top();

can straight go to the else block, as you don't need to check for stuff twice (don't have the energy to explain it better, just see code below)

You have != instead of == in infix[i]!='^'.

As you didn't post your code in [code]code_here[/code] tags, I can't tell on which lines, but you put chars from incorrect places : both line looks like this :postfix.push(infix[i]);.

Progesco wrote:

Pop remaining items in the stack to the output.

You're totally missing this part.

I suggest using getline instead of operator>>().

Don't use conio.h, to pause the console from closing use
cin.ignore(numeric_limits<streamsize>::max(), '\n');

I renamed your 'temp' stack, so it's name suggest what it does.

Here is the code I rewrote from yours, I reformatted for my eye sorry about that. I hope I didn't forgot to tell anything :).

#include <iostream>
#include <sstream>
#include <stack>
#include <limits>
#include <string>
using namespace std;

int priority(char a) {
    int temp;
    if (a == '^')
        temp = 1;
    else  if (a == '*' || a == '/')
        temp = 2;
    else  if (a == '+' || a == '-')
        temp = 3;
    return temp;
}

int main() {
    string infix;
    cout << "Enter an arithmetic expression: " << endl;
    getline(cin, infix);

    stack<char> operator_stack;

    stringstream output;

    for (unsigned i = 0; i < infix.length(); i++) {
        if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/' || infix[i] == '^') {
            while (!operator_stack.empty() && priority(operator_stack.top()) <= priority(infix[i])) {
                output << operator_stack.top();
                operator_stack.pop();
            }
            operator_stack.push(infix[i]);
        } else if (infix[i] == '(') {
            operator_stack.push(infix[i]);
        } else if (infix[i] == ')') {
            while (operator_stack.top() != '(') {
                output << operator_stack.top();
                operator_stack.pop();
            }
            operator_stack.pop();
        } else {
            output << infix[i];
        }
    }

    while (!operator_stack.empty()) {
        output << operator_stack.top();
        operator_stack.pop();
    }

    cout << output.str() << endl;

    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    return 0;
}

You don't check for mismatching parentheses, but I didn't implement it,

[Progesco]

thank you. it worked :D

btw, I don't know about sstream, so I change to"string output" and use "output.push_back()". it still works ^^