C++数组栈实现的中缀转后缀计算器计算失效，仅返回栈顶值

我用C++基于数组栈实现了中缀表达式转后缀表达式的转换器及计算器，但evaluatePostfix()函数无法正确计算操作数，仅返回栈顶值。

示例输入输出 #

Enter a infix expression: 1+4
your postfix expression is: 
14+

your result is: 
4

预期结果应为5，实际返回4。

相关代码 #

main()函数

int main()
{
      
      string infixExp = "";
      cout << "Enter a infix expression: ";
      cin >> infixExp;

      cout << "your postfix expression is: " << endl;
      infixToPostfix(infixExp);

      cout << endl;

      cout << "your result is: " << endl;
      cout << evaluatePostfix(infixExp) << endl;
}

evaluatePostfix()函数

int evaluatePostfix(string expression)
{
      ArrayStack<int> S;

      for (int i = 0; i < expression.length(); i++)
      {
            if (expression[i] == ' ' || expression[i] == ',') continue;

            else if(IsOperator(expression[i]))
            {
                  int operand2 = S.peek(); 
                  S.pop();
                  int operand1 = S.peek(); 
                  S.pop();

                  int result = PerformOperation(expression[i], operand1, operand2);

                  S.push(result);
            }

            else if(IsNumericDigit(expression[i]))
            {
                  int operand = 0;

                  while (i < expression.length() && IsNumericDigit(expression[i]))
                  {
                        operand = operand * 10 + expression[i] - '0';
                        i++;
                  }

                  i--;

                  S.push(operand);
            }
      }
      return S.peek();
}

辅助函数

bool IsNumericDigit(char C)
{
      if (C >= '0' && C <= '9')
      {
            return true;
      }

      else 
      {
            return false;
      }
}

bool IsOperator(char C)
{
      if (C == '+' || C == '-' || C == '*' || C == '/')
      {
            return true;
      }

      else 
      {
            return false;
      }
}

int PerformOperation(char operation, int operand1, int operand2)
{
      if (operation == '+')
      {
            return operand1 + operand2;
      }

      else if (operation == '-')
      {
            return operand1 - operand2;
      }

      else if (operation == '*')
      {
            return operand1 * operand2;
      }

      else if (operation == '/')
      {
            return operand1 / operand2;
      }

      else 
      {
            cout << "error" << endl;
      }

      return -1;
}

infixToPostfix()函数

void infixToPostfix(string s)
{
       ArrayStack<char> stackPtr;

       string postfixExp;

       for (int i = 0; i < s.length(); i++)
       {
            char ch = s[i];

            if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'))
            {
                  postfixExp += ch;
            }

            else if (ch == '(')
            {
                  stackPtr.push('(');
            }

            else if (ch == ')')
            {
                  while(stackPtr.peek() != '(')
                  {
                        postfixExp += stackPtr.peek();
                        stackPtr.pop();
                  }
                  stackPtr.pop();
            }

            else 
            {
                  while (!stackPtr.isEmpty() && prec(s[i]) <= prec(stackPtr.peek()))
                  {
                        postfixExp += stackPtr.peek();
                        stackPtr.pop();
                  }
                  stackPtr.push(ch);
            }
       }

       while (!stackPtr.isEmpty())
       {
            postfixExp += stackPtr.peek();
            stackPtr.pop();
       }
       
       cout << postfixExp << endl;
}

问题原因及解决方法 #

核心错误

你调用evaluatePostfix()时，传入的是原始的中缀表达式infixExp，而非转换后的后缀表达式。infixToPostfix()仅输出了后缀结果，但未将其返回保存，导致evaluatePostfix处理的是未转换的1+4，而非正确的14+。

处理中缀表达式1+4时，evaluatePostfix的执行流程：

1. 读取'1'，压入栈，栈内为[1]
2. 读取'+'，尝试弹出两个操作数，但此时栈内只有一个元素，后续操作会因栈空出现异常行为
3. 读取'4'，压入栈，栈内最终为[4]
4. 返回栈顶值4，导致结果错误

修复步骤

1. 修改infixToPostfix函数，使其返回后缀字符串：

string infixToPostfix(string s)
{
       ArrayStack<char> stackPtr;
       string postfixExp;

       for (int i = 0; i < s.length(); i++)
       {
            char ch = s[i];

            if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'))
            {
                  postfixExp += ch;
            }

            else if (ch == '(')
            {
                  stackPtr.push('(');
            }

            else if (ch == ')')
            {
                  while(stackPtr.peek() != '(')
                  {
                        postfixExp += stackPtr.peek();
                        stackPtr.pop();
                  }
                  stackPtr.pop();
            }

            else 
            {
                  while (!stackPtr.isEmpty() && prec(s[i]) <= prec(stackPtr.peek()))
                  {
                        postfixExp += stackPtr.peek();
                        stackPtr.pop();
                  }
                  stackPtr.push(ch);
            }
       }

       while (!stackPtr.isEmpty())
       {
            postfixExp += stackPtr.peek();
            stackPtr.pop();
       }
       
       return postfixExp;
}

2. 在main函数中保存转换后的后缀表达式，再传入evaluatePostfix：

int main()
{
      string infixExp = "";
      cout << "Enter a infix expression: ";
      cin >> infixExp;

      string postfixExp = infixToPostfix(infixExp);
      cout << "your postfix expression is: " << endl;
      cout << postfixExp << endl;

      cout << endl;

      cout << "your result is: " << endl;
      cout << evaluatePostfix(postfixExp) << endl;
}

3. 补充运算符优先级函数prec：

int prec(char c)
{
    if(c == '+' || c == '-')
        return 1;
    if(c == '*' || c == '/')
        return 2;
    return 0;
}

4. 添加错误处理：在evaluatePostfix遇到运算符时，检查栈内是否有至少两个操作数：

else if(IsOperator(expression[i]))
{
      if(S.isEmpty()) {
            cout << "Invalid expression" << endl;
            exit(1);
      }
      int operand2 = S.peek(); 
      S.pop();
      if(S.isEmpty()) {
            cout << "Invalid expression" << endl;
            exit(1);
      }
      int operand1 = S.peek(); 
      S.pop();

      int result = PerformOperation(expression[i], operand1, operand2);

      S.push(result);
}

内容的提问来源于stack exchange，提问作者evantuazon