9

My lecturer gave me an assignment to create a program to convert and infix expression to postfix using Stacks. I've made the stack classes and some functions to read the infix expression.

But this one function, called convertToPostfix(char * const inFix, char * const postFix) which is responsible to convert the inFix expression in the array inFix to the post fix expression in the array postFix using stacks, is not doing what it suppose to do. Can you guys help me out and tell me what I'm doing wrong?

The following is code where the functions to convert from inFix to postFix is and convertToPostfix(char * const inFix, char * const postFix) is what I need help fixing:

 void ArithmeticExpression::inputAndConvertToPostfix()
    {
       char inputChar; //declaring inputChar
       int i = 0; //inizalize i to 0

       cout << "Enter the Arithmetic Expression(No Spaces): ";

       while( ( inputChar = static_cast<char>( cin.get() ) ) != '\n' )
       {
          if (i >= MAXSIZE) break; //exits program if i is greater than or equal to 100

          if(isdigit(inputChar) || isOperator(inputChar))
          {
             inFix[i] = inputChar; //copies each char to inFix array
             cout << inFix[i] << endl;
          }
          else
             cout << "You entered an invalid Arithmetic Expression\n\n" ;

          }

          // increment i;
          i++;
          convertToPostfix(inFix, postFix);


       }




    bool ArithmeticExpression::isOperator(char currentChar)
    {

        if(currentChar == '+')
            return true;
        else if(currentChar == '-')
            return true;
        else if(currentChar == '*')
            return true;
        else if(currentChar == '/')
            return true;
        else if(currentChar == '^')
            return true;
        else if(currentChar == '%')
            return true;
        else
            return false;
    }

    bool ArithmeticExpression::precedence(char operator1, char operator2)
    {
        if ( operator1 == '^' )
           return true;
        else if ( operator2 == '^' )
           return false;
        else if ( operator1 == '*' || operator1 == '/' )
           return true;
        else if ( operator1 == '+' || operator1 == '-' )
           if ( operator2 == '*' || operator2 == '/' )
              return false;
           else
              return true;

        return false;
    }

   void ArithmeticExpression::convertToPostfix(char * const inFix, char * const postFix)
        {
           Stack2<char> stack;

           const char lp = '(';

           stack.push(lp); //Push a left parenthesis ‘(‘ onto the stack.

           strcat(inFix,")");//Appends a right parenthesis ‘)’ to the end of infix.

          // int i = 0;
           int j = 0;

           if(!stack.isEmpty())
           {

               for(int i = 0;i < 100;){

                   if(isdigit(inFix[i]))
                   {
                        postFix[j] = inFix[i];
                        cout << "This is Post Fix for the first If: " << postFix[j] << endl;
                        i++;
                        j++;
                   }

                    if(inFix[i] == '(')
                   {
                       stack.push(inFix[i]);
                       cout << "The InFix was a (" << endl;
                       i++;
                       //j++;
                   }

                    if(isOperator(inFix[i]))
                               {
                            char operator1 = inFix[i];

                            cout << "CUrrent inFix is a operator" << endl;
                                   if(isOperator(stack.getTopPtr()->getData()))
                                       {
                                       cout << "The stack top ptr is a operator1" << endl;
                                       char operator2 = stack.getTopPtr()->getData();
                                           if(precedence(operator1,operator2))
                                           {
                                               //if(isOperator(stack.getTopPtr()->getData())){
                                                   cout << "The stack top ptr is a operato2" << endl;
                                                   postFix[j] = stack.pop();
                                                   cout << "this is post fix " << postFix[j] << endl;
                                                   i++;
                                                   j++;
                                              // }

                                           }

                                       }
                                   else

                                       stack.push(inFix[i]);
                                   // cout << "Top Ptr is a: "<< stack.getTopPtr()->getData() << endl;



                               }

                    for(int r = 0;r != '\0';r++)
                        cout << postFix[r] << " ";

                        if(inFix[i] == ')')
                       {
                           while(stack.stackTop()!= '(')
                         {
                               postFix[j] = stack.pop();
                               i++;
                               j++;
                                }
                           stack.pop();

                            }
                       }
           }

                   }

Note the function convertToPostfix was made using this algorithm:

  • Push a left parenthesis ‘(‘ onto the stack.
  • Append a right parenthesis ‘)’ to the end of infix.

  • While the stack is not empty, read infix from left to right and do the following:

    • If the current character in infix is a digit, copy it to the next element of postfix.
    • If the current character in infix is a left parenthesis, push it onto the stack.

    • If the current character in infix is an operator,

      • Pop operator(s) (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and insert the popped operators in postfix.
      • Push the current character in infix onto the stack.
    • If the current character in infix is a right parenthesis
      • Pop operators from the top of the stack and insert them in postfix until a left parenthesis is at the top of the stack.
      • Pop (and discard) the left parenthesis from the stack.
Peter O.
  • 32,158
  • 14
  • 82
  • 96
Reggie Escobar
  • 99
  • 1
  • 1
  • 3
  • 1
    Unless you're feeling masochistic, Googling for "recursive descent" or (especially) "shunting yard algorithm" will probably be rather helpful (if you're already trying to use one of these, I apologize -- at least at first glance I didn't recognize it as implementing either). – Jerry Coffin Oct 02 '12 at 03:23
  • I followed the algorithm that i just edited in my post that was given by my lecturer but i don't seem to make it work. – Reggie Escobar Oct 02 '12 at 03:31
  • 3
    You should team up with [this person](http://stackoverflow.com/questions/12684085/infix-operation-to-postfix-using-stacks). He asked the same question at the same time you did. – Blastfurnace Oct 02 '12 at 03:34
  • We are in the same class but different group. – Reggie Escobar Oct 02 '12 at 03:37
  • 1
    So, stepping through this code in the debugger, what does it tell you? Don't tell me you don't know what a debugger is or how to use it or that you haven't tried to use it or tried but helplessly failed. C'mon. You can't do it with your brain alone, use the tool. – Alexey Frunze Oct 02 '12 at 04:45
  • i did. Code crashes now. I edited the code in the post. – Reggie Escobar Oct 02 '12 at 06:59
  • His class is over, it's a simple exercise, it's a waste of the effort. – flup Jan 24 '13 at 17:36

6 Answers6

7

This is basically a comment to the answer from Yuushi.

  • The outer while(!stack.empty()) loop is wrong. just remove it. (keep the loop body ofc). At the end of the function, check that the stack is empty, else the expression had syntax errors.
  • As Yuushi already said the precedence function looks bogus. First you should give the parameters better names: one is the operator to the left, and the other to the right. (Right now you call it precedence(rightOp, leftOp)). Then you should document what the result means - right now you return true if a rOp b lOp c == (a rOp b) lOp c (yes, the operator order doesn't match what you call - "+" and "-" are not the same in both orders for example).
  • If you find a new operator you need to loop over the old operators on the stack, for example after reading a - b * c your output is a b c and the stack is [- *]. now you read a +, and you need to pop both operators, resulting in a b c * -. I.e., the input a - b * c + d should result in a b c * - d +

Update: appended complete solution (based on Yuushi's answer): 

bool isOperator(char currentChar)
{
    switch (currentChar) {
    case '+':
    case '-':
    case '*':
    case '/':
    case '^':
    case '%':
        return true;
    default:
        return false;
    }
}

// returns whether a `lOp` b `rOp` c == (a `lOp` b) `rOp` c
bool precedence(char leftOperator, char rightOperator)
{
    if ( leftOperator == '^' ) {
        return true;
    } else if ( rightOperator == '^' ) {
        return false;
    } else if ( leftOperator == '*' || leftOperator == '/' || leftOperator == '%' ) {
        return true;
    } else if ( rightOperator == '*' || rightOperator == '/' || rightOperator == '%' ) {
        return false;
    }

    return true;
}

#include <stdexcept>
#include <cctype>
#include <sstream>
#include <stack>
std::string convertToPostfix(const std::string& infix)
{
    std::stringstream postfix; // Our return string
    std::stack<char> stack;
    stack.push('('); // Push a left parenthesis ‘(‘ onto the stack.

    for(std::size_t i = 0, l = infix.size(); i < l; ++i) {
        const char current = infix[i];

        if (isspace(current)) {
            // ignore
        }
        // If it's a digit or '.' or a letter ("variables"), add it to the output
        else if(isalnum(current) || '.' == current) {
            postfix << current;
        }

        else if('(' == current) {
            stack.push(current);
        }

        else if(isOperator(current)) {
            char rightOperator = current;
            while(!stack.empty() && isOperator(stack.top()) && precedence(stack.top(), rightOperator)) {
                postfix << ' ' << stack.top();
                stack.pop();
            }
            postfix << ' ';
            stack.push(rightOperator);
        }

        // We've hit a right parens
        else if(')' == current) {
            // While top of stack is not a left parens
            while(!stack.empty() && '(' != stack.top()) {
                postfix << ' ' << stack.top();
                stack.pop();
            }
            if (stack.empty()) {
                throw std::runtime_error("missing left paren");
            }
            // Discard the left paren
            stack.pop();
            postfix << ' ';
        } else {
            throw std::runtime_error("invalid input character");
        }
    }


    // Started with a left paren, now close it:
    // While top of stack is not a left paren
    while(!stack.empty() && '(' != stack.top()) {
        postfix << ' ' << stack.top();
        stack.pop();
    }
    if (stack.empty()) {
        throw std::runtime_error("missing left paren");
    }
    // Discard the left paren
    stack.pop();

    // all open parens should be closed now -> empty stack
    if (!stack.empty()) {
        throw std::runtime_error("missing right paren");
    }

    return postfix.str();
}

#include <iostream>
#include <string>
int main()
{
    for (;;) {
        if (!std::cout.good()) break;
        std::cout << "Enter the Arithmetic Expression: ";
        std::string infix;
        std::getline(std::cin, infix);
        if (infix.empty()) break;

        std::cout << "Postfix: '" << convertToPostfix(infix) << "'\n";
    }

    return 0;
}
Stefan
  • 5,304
  • 2
  • 25
  • 44
  • What does the "for(;;)" do? – Steven Nov 03 '15 at 22:48
  • @Steven it's just shorten than writing `while (true)` – vallentin Nov 05 '15 at 16:21
  • [Endless loop in C/C++](http://stackoverflow.com/questions/20186809/endless-loop-in-c-c) – Stefan Nov 05 '15 at 21:47
  • According to your `precedence` function, `a ^ b + c == ( a ^ b ) + c`. The precedence of `+` operator is higher than `^`. Shouldn't `a ^ b + c == a ^ ( b + c )`? – crisron May 23 '16 at 02:34
  • @crisron a ^ b + c is definitely equal to (a^b) + c. The ^ operator has the highest precedence, thus it is applied to operands a and b. Then the result of that operation is added to c in this scenario. – h0r53 Jun 17 '16 at 03:25
  • @CaitLANJenner [This](http://en.cppreference.com/w/c/language/operator_precedence) page says that `+` has higher precedence than `^`. – crisron Jun 17 '16 at 05:14
  • @crisron Ahh, I see what you're saying. Mathematically the "power" operation ^ has higher precedence than addition, every time. However, if you're talking about a c++ operator+ versus c++ operator^, then yes you are correct. Although, it appears that the original poster was asking about evaluating an arithmetic expression. So ultimately it depends on what you're trying to do. If you want to perform a mathematical calculation, ^ has higher precedence. If you're evaluating a C++ expression, + has higher precedence (this would be the precedence compilers consider when assembling your code). – h0r53 Jun 17 '16 at 12:22
2

So there are a number of problems with your code. I'll post what (should be) a corrected solution, which has copious comments to explain what's happening and where you've made mistakes. A few things up front:

  1. I'll use std::string instead of char * because it makes things much cleaner, and honestly, you should be using it in C++ unless you have a very good reason not to (such as interoperability with a C library). This version also returns a string instead of taking a char * as a parameter.

  2. I'm using the stack from the standard library, <stack>, which is slightly different to your home-rolled one. top() shows you the next element without removing it from the stack, and pop() returns void, but removes the top element from the stack.

  3. It's a free function, not part of a class, but that should be easy to modify - it's simply easier for me to test this way.

  4. I'm not convinced your operator precedence tables are correct, however, I'll let you double check that.

#include <stack>
#include <cctype>
#include <iostream>

std::string convertToPostfix(std::string& infix)
{
    std::string postfix; //Our return string
    std::stack<char> stack;
    stack.push('('); //Push a left parenthesis ‘(‘ onto the stack.
    infix.push_back(')');

    //We know we need to process every element in the string,
    //so let's do that instead of having to worry about
    //hardcoded numbers and i, j indecies
    for(std::size_t i = 0; i < infix.size(); ++i) {

        //If it's a digit, add it to the output
        //Also, if it's a space, add it to the output 
        //this makes it look a bit nicer
        if(isdigit(infix[i]) || isspace(infix[i])) {
            postfix.push_back(infix[i]);
        }

        //Already iterating over i, so 
        //don't need to worry about i++
        //Also, these options are all mutually exclusive,
        //so they should be else if instead of if.
        //(Mutually exclusive in that if something is a digit,
        //it can't be a parens or an operator or anything else).
        else if(infix[i] == '(') {
            stack.push(infix[i]);
        }

        //This is farily similar to your code, but cleaned up. 
        //With strings we can simply push_back instead of having
        //to worry about incrementing some counter.
        else if(isOperator(infix[i]))
        {
            char operator1 = infix[i];
            if(isOperator(stack.top())) {
                while(!stack.empty() && precedence(operator1,stack.top())) {
                    postfix.push_back(stack.top());
                    stack.pop();
                }
            }
            //This shouldn't be in an else - we always want to push the
            //operator onto the stack
            stack.push(operator1);
        }    

        //We've hit a right parens - Why you had a for loop
        //here originally I don't know
        else if(infix[i] == ')') {
            //While top of stack is not a right parens
            while(stack.top() != '(') {
            //Insert into postfix and pop the stack
                postfix.push_back(stack.top());
                stack.pop();
            }
            // Discard the left parens - you'd forgotten to do this
            stack.pop(); 
        }
    }

    //Remove any remaining operators from the stack
    while(!stack.empty()) {
        postfix.push_back(stack.top());
        stack.pop();
    }
}
Yuushi
  • 25,132
  • 7
  • 63
  • 81
  • 1
    I added somecomments as answer (needed more space and format stuff) - perhaps you want to improve your answer :) – Stefan Jan 19 '13 at 12:35
  • @Stefan Thanks, all good catches. I've updated my answer, hopefully it's error free this time (and this is a lesson in why I should write tests!) – Yuushi Jan 19 '13 at 13:20
0

Here's mine using C with multiple digits evaluation.

#include <stdio.h>
#include <math.h>
#define MAX 50
void push(char[],char);
void in_push(double[], double);
int pop();
int prec(char);
double eval(char[],int,double[]);
int top = 0;
void main() {
double eval_stack[MAX];
int op_count=0;
char stack[MAX], exps[MAX], symbols[MAX];
int i=0,j=0,len,check;
while((symbols[i]=getchar())!='\n') {
if(symbols[i]!=' ' || symbols[i]!='\t') {
if(symbols[i]=='+' || symbols[i]=='-' || symbols[i]=='/' || symbols[i]=='*' || symbols[i]=='^')
op_count++;
i++;
}
}
symbols[i]='#';
symbols[++i]='\0';
len = strlen(symbols);
stack[top] = '#';
for(i=0; i<=len; i++) {
if(symbols[i]>='a'  && symbols[i]<='z') {
exps[j]=symbols[i];
j++;
}
switch(symbols[i]) {
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
//if(symbols[i]>='a'  && symbols[i]<='z') {
exps[j]=symbols[i];
j++;
break;
case '+': case '-': case '*': case '/': case '^':
exps[j++] = ' ';
while(prec(symbols[i]) <= prec(stack[top])) {

             exps[j] = stack[top];
             pop();
             //printf("\n\t\t%d\t\t%d\n", top,j);
                j++;


}
if(prec(symbols[i]) > prec(stack[top])) {
push(stack,symbols[i]);
}
break;
case '(':
push(stack,symbols[i]);
break;
case ')':
while(stack[top]!='(') {
      exps[j] = stack[top];
       pop();
      j++;

}
pop();
break;
case '#':
exps[j++] = ' ';
while(stack[top]!='#') {
      exps[j] = stack[top];
       pop();
       j++;

}
pop();
break;
}
}
exps[j]='\0';
printf("Postfix: %s", exps);
for(i=0; i<j; i++)
if(exps[i]=='a')
check = 1;
if(check!=1)
printf("\nSolution: %.1f", eval(exps,j,eval_stack));
}

double eval(char exps[],int exps_len,double eval_stack[]) {
    int i; int len=exps_len,temp;
    double in_temp[MAX],t;
    int count,power,j,in_count;
    count=power=j=t=in_count=0;
    double result;
for(i=0; i<len; i++) {
switch(exps[i]) {
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
in_temp[i] = exps[i]-'0';
j=i+1;
while(exps[j]>='0' && exps[j]<='9') {
in_temp[j] = exps[j]-'0';
j++; // 2
}
count = i; // 3
while(in_temp[count]<='0' && in_temp[count]<='9') {
power = (j-count)-1;
t = t + in_temp[count]*(pow(10,power));
power--;
count++;
}
in_push(eval_stack,t);
i=j-1;
t=0;
break;
case '+':
temp = pop();
pop();
result = eval_stack[temp] + eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '-':
temp = pop();
pop();
result = eval_stack[temp] - eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '*':
temp = pop();
pop();
result = eval_stack[temp] * eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '/':
temp = pop();
pop();
result = eval_stack[temp] / eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '^':
temp = pop();
pop();
result = pow(eval_stack[temp],eval_stack[temp+1]);
in_push(eval_stack,result);
break;
}
}
return eval_stack[top];
}
int prec(char a) {
if(a=='^')
return 3;
else if(a=='*' || a=='/' || a=='%')
return 2;
else if(a=='+' || a=='-')
return 1;
else if(a=='(')
return 0;
else
return -1;
}

void push(char stack[], char ele) {
    if(top>=MAX) {
    printf("\nStack Overflow");
    exit(1);
    }
stack[++top] = ele;
}
void in_push(double stack[], double ele) {
    if(top>=MAX) {
    printf("\nStack Overflow");
    exit(1);
    }
stack[++top] = ele;
}
int pop() {
    if(top<0) {
    printf("\nStack Underflow");
    exit(1);
    }

top = top - 1;
return top;
}
rajatbarman
  • 149
  • 1
  • 6
0

This is my implementation of converting infix to postfix expression

//Infix to Postfix conversion
#include <bits/stdc++.h> 
using namespace std; 

bool isoperator(char c)                                            // function to check         if the character is an operator
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
    return true;
else
    return false;
}

int precedence(char c)                // function to given the precedence of the operators
{
if(c == '^') 
    return 3; 
else if(c == '*' || c == '/') 
    return 2; 
else if(c == '+' || c == '-') 
    return 1; 
else
    return -1; 
}

void infixToPostfix(string s)                          // funtion to convert infix to postfix
{
stack<char>st;
string postfix;
for(int i=0;i<s.length();i++)
{
    if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))         // if the given character is alphabet add it to the postfix string
        postfix+=s[i];
    else if(s[i]=='(')                                         // if the given character is "(" add it to the postfix string 
        st.push('(');
    else if(s[i]==')')                                         // if we find a closing bracket we pop everything from stack till opening bracket and add it to postfix string
    {
        while(st.top()=='(' && !st.empty())
        {
            postfix+=st.top();
            st.pop();
        }
        if(st.top()=='(')                                      // popping the opening bracket
            st.pop();
    }  
    else if(isoperator(s[i]))                                 // if we find a operator
    {
        if(st.empty())                                        // if stack is empty add it to the stack
            st.push(s[i]);
        else
        {
            if(precedence(s[i])>precedence(st.top()))       // if operator precedence is grater push it in stack
                st.push(s[i]);
            else if((precedence(s[i])==precedence(st.top()))&&(s[i]=='^'))  // unique case for ^ operator
                st.push(s[i]);
            else
            {
                while((!st.empty())&&(precedence(s[i])<=precedence(st.top())))   // if precedence of st.top() is greater than s[i] adding it the postfix string
                {
                    postfix+=st.top();
                    st.pop();
                }
                st.push(s[i]);       // pushing s[i] in the stack 
            }
        }
    }
}
while(!st.empty())                  // popping the remaining items from the stack and adding it to the postfix string
{ 
    postfix+=st.top();
    st.pop();
} 
cout<<postfix<<endl;               // printing the postfix string
}

int main() 
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin>>s;
infixToPostfix(s); 
return 0;
}

Example:

Input: a+b*(c^d-e)^(f+g*h)-i

Output: abcd^efgh*+i-(^-(*+

ps: If you find any mistakes, comment below :)

confused_
  • 1,133
  • 8
  • 10
-1

C++ implementation is given below:

  void infix2postfix(string s)
   {
     stack<char>st;
     for(int i=0; i<s.length(); i++)
     {
        if(isdigit(s[i]) || isalpha(s[i]))  cout<<s[i];
        else if( s[i]==')' )
        {
           while(st.top()!='(')
           {
                cout<<st.top();
                st.pop();
           }
          st.pop();
        }

        else st.push(s[i]);
      }
   }
rashedcs
  • 3,588
  • 2
  • 39
  • 40
-2

Operator Precedence is the problem in this case. The correct operator precedence in descending order is:

mul, div, mod   << *, /, % >>
add, sub        << +, - >>
XOR             << ^ >>

In the question above consider the precedence function

bool ArithmeticExpression::precedence(char operator1, char operator2)
{
    if ( operator1 == '^' )
       return true;
    else if ( operator2 == '^' )
       return false;
    else if ( operator1 == '*' || operator1 == '/' )
       return true;
    else if ( operator1 == '+' || operator1 == '-' )
       if ( operator2 == '*' || operator2 == '/' )
          return false;
       else
          return true;
    return false;
}

for each value in operator1 corresponding value of operator2 should be checked for precedence, according to OPERATOR PRECEDENCE TABLE mentioned above. Do not return any value without proper comparison.

rohank
  • 81
  • 1
  • 9