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

2022-01-22 00:00:00 stack c++ infix-notation postfix-notation

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

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.

但是这个函数叫做 convertToPostfix(char * const inFix, char * const postFix) 负责将数组 inFix 中的 inFix 表达式转换为数组 postFix 中的后置表达式堆栈，没有做它应该做的事情.你们能帮帮我，告诉我我做错了什么吗?

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?

以下是从 inFix 转换为 postFix 的函数所在的代码，convertToPostfix(char * const inFix, char * const 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:

 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() ) ) != '
' )
       {
          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

" ;

          }

          // 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 != '';r++)
                        cout << postFix[r] << " ";

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

                            }
                       }
           }

                   }

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

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,

  • 在栈顶弹出操作符(如果有的话)，同时它们的优先级等于或高于当前操作符，并将弹出的操作符插入到后缀中.
  • 将中缀中的当前字符压入堆栈.
  • 从栈顶弹出运算符并将它们插入到后缀中，直到左括号位于栈顶.
  • 从堆栈中弹出(并丢弃)左括号.

推荐答案

这基本上是对Yuushi回答的评论.

This is basically a comment to the answer from Yuushi.

  • 外部 while(!stack.empty()) 循环是错误的.只需将其删除.(保持c的循环体).在函数结束时，检查堆栈是否为空，否则表达式有语法错误.
  • 正如 Yuushi 已经说过的，优先功能看起来很假.首先你应该给参数起一个更好的名字:一个是左边的操作符，另一个是右边的.(现在你称之为 precedence(rightOp, leftOp)).然后你应该记录结果的含义 - 现在你返回 true if a rOp b lOp c == (a rOp b) lOp c (是的，操作员的顺序与你所说的不匹配 -例如，两个顺序中的+"和-"不一样).
  • 如果你找到一个新的操作符，你需要遍历堆栈中的旧操作符，例如在读取 a - b * c 之后你的输出是 abc 并且堆栈是 [- *].现在你读到了一个+，你需要弹出两个操作符，结果是a b c * -.即，输入 a - b * c + d 应该导致 a b c * - d +
  • 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 +

更新:附加完整解决方案(基于 Yuushi 的回答):

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) << "'
";
    }

    return 0;
}

相关文章