Convert from infix expression to postfix (C ++) using Stacks

Question

My teacher instructed me to create a program for converting and infix expression to postfix using Stacks. I made stack classes and some functions for reading infix expressions.

But this one function, called convertToPostfix(char * const inFix, char * const postFix) , which is responsible for converting the inFix expression into an inFix array into a post fix expression in a postFix array using stacks, does not do what it assumed. Can you guys help me and tell me what I'm doing wrong?

Below is the code in which the functions for converting from inFix to postFix and convertToPostfix(char * const inFix, char * const postFix) is what I need to fix the help:

  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 that the convertToPostfix function was created using this algorithm:

• Press the left bracket '(' onto the stack.
• Add the right bracket ") to the end of the infix.

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

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

  • If the current character in infix is ​​an operator,

    • Pop statements (if any) are at the top of the stack, while they have equal or higher priority than the current statement and insert pop-up statements in the postfix.
    • Paste the current character into the infix on the stack.
  • If the current character in infix is ​​a right bracket
    • Pop operators from the top of the stack and insert them into the postfix until the left bracket is at the top of the stack.
    • Hit (and drop) the left bracket from the stack.

Answer 1

This is basically a comment on the answer from Yuushi.

• Invalid while loop (! Stack.empty ()). just delete it. (save the body of cycle c). At the end of the function, check that the stack is empty, otherwise the expression has syntax errors.
• As Yushi already said, the priority function looks fictitious. First you have to give the parameters the best names: one is the operator on the left and the other on the right. (Right now you call it precedence(rightOp, leftOp) ). Then you should document what the result means - right now you are returning true if a rOp b lOp c == (a rOp b) lOp c (yes, the operator order does not match what you call - "+" and "-" , for example, do not match in both orders).
• If you find a new operator, you need to iterate over the old operators on the stack, for example, after reading a - b * c your output is abc , and the stack is [- *] . now you read + , and you need to stroke both operators, the result is abc * - . I., input a - b * c + d should lead to abc * - d +

Update : added complete solution (based on Yuushi 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 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; } 

Answer 2

So there are a number of problems with your code. I will write that there (should be) a fixed solution in which there are abundant comments to explain what is happening and where you made mistakes. A few things to come:

• I use std::string instead of char * because it makes things a lot cleaner, and to be honest, you should use them in C++ if you have no reason for this (e.g. compatibility with the C library). This version also returns string instead of taking char * as a parameter.

• I use the stack from the standard <stack> library, which is slightly different from your home library. top() shows you the next element without removing it from the stack, and pop() returns void , but removes the top element from the stack.

• This is a free feature, not part of the class, but it should be easy to modify - it is just easier for me to test this way.

• I'm not sure that your operator priority tables are correct, however I will let you double check this.

---

 #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 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 a digit, add it to the output //Also, if it 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(); } } 

Answer 3

Here I use C with multiple digits estimation.

 #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; } 

Answer 4

C ++ implementation:

---

  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]); } } 

Answer 5

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

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

In this question, we consider the priority 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, the corresponding value of operator2 must be checked for priority, according to the PRECEDENCE TABLE OPERATOR TABLE mentioned above. Do not return values ​​without proper comparison.