使用堆栈从中缀表达式转换为后缀 (C++)

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

提问by Reggie Escobar

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.

我的讲师给了我一项作业，要创建一个程序，使用 Stacks 将中缀表达式转换为后缀。我已经制作了堆栈类和一些函数来读取中缀表达式。

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?

但是这个被调用的函数convertToPostfix(char * const inFix, char * const postFix)负责使用堆栈将数组 inFix 中的 inFix 表达式转换为数组 postFix 中的后修复表达式，它没有做它应该做的事情。你们能帮我一下，告诉我我做错了什么吗？

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:

以下是从 inFix 转换为 postFix 的函数所在的代码，convertToPostfix(char * const inFix, char * const postFix)也是我需要帮助修复的代码：

 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 != '
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;
}
';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:

请注意，函数 convertToPostfix 是使用此算法生成的：

• 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.

• 将左括号 '(' 压入堆栈。
• 在中缀末尾附加一个右括号“)”。

• 当堆栈不为空时，从左到右读取中缀并执行以下操作：

  • 如果中缀中的当前字符是数字，则将其复制到后缀的下一个元素。
  • 如果中缀中的当前字符是左括号，则将其压入堆栈。

  • 如果中缀中的当前字符是运算符，

    • 当它们具有等于或高于当前运算符的优先级时，在堆栈顶部弹出运算符（如果有），并将弹出的运算符插入后缀。
    • 将中缀中的当前字符压入堆栈。
  • 如果中缀中的当前字符是右括号
    • 从堆栈顶部弹出运算符并将它们插入后缀，直到左括号位于堆栈顶部。
    • 从堆栈中弹出（并丢弃）左括号。

回答by Stefan

This is basically a comment to the answer from Yuushi.

这基本上是对 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 * cyour output is a b cand 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 + dshould result in a b c * - d +

• 外部 while(!stack.empty()) 循环是错误的。只需删除它。（保持循环体 ofc）。在函数结束时，检查堆栈是否为空，否则表达式有语法错误。
• 正如 Yuushi 已经说过的，优先函数看起来很假。首先，您应该为参数提供更好的名称：一个是左侧的运算符，另一个是右侧的运算符。（现在你称之为precedence(rightOp, leftOp)）。然后你应该记录结果的含义 - 现在你返回 true if a rOp b lOp c == (a rOp b) lOp c（是的，运算符顺序与你所说的不匹配 - 例如，“+”和“-”在两个订单中不相同）。
• 如果你找到一个新的操作符，你需要遍历堆栈上的旧操作符，例如在读取a - b * c你的输出 isa b c和堆栈 is 之后[- *]。现在你读了一个+，你需要弹出两个运算符，结果是a b c * -. 即，输入a - b * c + d应该导致a b c * - d +

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

更新：附加完整的解决方案（基于 Yuushi 的回答）：

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

回答by Yuushi

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::stringinstead 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 Clibrary). This version also returns a stringinstead 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 withoutremoving 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.

1. 我将使用std::string而不是char *因为它使事情变得更清晰，老实说，C++除非您有很好的理由不这样做（例如与C库的互操作性），否则您应该使用它。此版本还返回 astring而不是将 achar *作为参数。

2. 我正在使用标准库中的堆栈，<stack>，这与您在家中推出的堆栈略有不同。top()显示下一个元素而不从堆栈中删除它，并pop()返回void，但从堆栈中删除顶部元素。

3. 这是一个免费的函数，不是类的一部分，但应该很容易修改——我用这种方式测试更容易。

4. 我不相信您的运算符优先级表是正确的，但是，我会让您仔细检查一下。

---

---

#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]='
  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]);
      }
   }
';
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]='
mul, div, mod   << *, /, % >>
add, sub        << +, - >>
XOR             << ^ >>
';
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;
}

回答by rajatbarman

Here's mine using C with multiple digits evaluation.

这是我使用 C 与多位数字评估。

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

回答by rashedcs

C++ implementation is given below:

C++实现如下：

---

---

##代码##

回答by rohank

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

在这种情况下，运算符优先级是问题所在。按降序排列的正确运算符优先级是：

##代码##

In the question above consider the precedence function

在上面的问题中考虑优先函数

##代码##

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.

对于 operator1 中的每个值，应根据上面提到的 OPERATOR PRECEDENCE TABLE 检查 operator2 对应值的优先级。如果没有适当的比较，不要返回任何值。