c++ - スタックを使用して中置式から後置式 (C++) に変換する

Question

私の講師は、スタックを使用して式を後置に変換および挿入するプログラムを作成するという課題を与えました。中置式を読み取るためのスタック クラスといくつかの関数を作成しました。

しかし、convertToPostfix(char * const inFix, char * const postFix)スタックを使用して配列 inFix 内の inFix 式を配列 postFix 内の事後修正式に変換する役割を担うこの 1 つの関数は、想定どおりの動作をしていません。皆さんは私を助けて、私が間違っていることを教えてもらえますか?

以下は、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 != '\0';r++)
                        cout << postFix[r] << " ";

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

                            }
                       }
           }

                   }

関数 convertToPostfix は、このアルゴリズムを使用して作成されていることに注意してください。

• 左括弧 '(' をスタックにプッシュします。
• infix の末尾に右括弧 ')' を追加します。

• スタックが空でない間、左から右に infix を読み取り、次のことを行います。

  • infix の現在の文字が数字の場合、postfix の次の要素にコピーします。
  • infix の現在の文字が左括弧である場合、それをスタックにプッシュします。

  • infix の現在の文字が演算子の場合、

    • 現在の演算子と同等またはそれ以上の優先順位を持つスタックの一番上に演算子 (存在する場合) をポップし、ポップされた演算子を後置に挿入します。
    • infix 内の現在の文字をスタックにプッシュします。
  • infix の現在の文字が右括弧の場合
    • スタックの一番上から演算子をポップし、左括弧がスタックの一番上になるまで後置に挿入します。
    • スタックから左括弧をポップ (および破棄) します。

Answer 1

これは基本的に、ユウシからの回答に対するコメントです。

• 外側の while(!stack.empty()) ループが間違っています。それを取り除くだけです。(ループ本体は c のままにします)。関数の最後で、スタックが空であることを確認してください。それ以外の場合、式に構文エラーがありました。
• Yuushi が既に言ったように、優先順位関数は偽物に見えます。最初に、パラメーターに適切な名前を付ける必要があります。1 つは左側の演算子で、もう 1 つは右側の演算子です。(今は と呼んでいますprecedence(rightOp, leftOp))。次に、結果が何を意味するかを文書化する必要があります-現在、trueを返す場合a rOp b lOp c == (a rOp b) lOp c(はい、演算子の順序が呼び出したものと一致しません-たとえば、「+」と「-」は両方の順序で同じではありません)。
• 新しい演算子を見つけた場合は、スタック上の古い演算子をループする必要があります。たとえばa - b * c、出力を読み取った後a b c、スタックは[- *]です。を読み取り、+両方の演算子をポップする必要があり、結果は になりa b c * -ます。つまり、入力のa - b * c + d結果はa b c * - d +

更新：追加の完全なソリューション（Yuushiの回答に基づく）：

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

Answer 2

したがって、コードには多くの問題があります。何が起こっているのか、どこで間違いを犯したのかを説明するための豊富なコメントを含む、修正されたソリューション (であるべき) を投稿します。前もっていくつかのこと：

1. std::string代わりに を使用します。char *よりクリーンになるからです。正直なところ、使用しC++ない非常に正当な理由 (Cライブラリとの相互運用性など) がない限り、使用する必要があります。stringこのバージョンでは、パラメーターとして aを受け取る代わりに、a も返しchar *ます。

2. 標準ライブラリのスタックを使用していますが<stack>、これは自作のものとは少し異なります。スタックから削除せずtop()に次の要素を表示し、 を返しますが、スタックから一番上の要素を削除します。pop()void

3. これは無料の関数であり、クラスの一部ではありませんが、簡単に変更できるはずです。この方法でテストする方が簡単です。

4. 演算子の優先順位表が正しいとは確信していませんが、再確認させてください。

---

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

Answer 3

この場合、演算子の優先順位が問題になります。降順での正しい演算子の優先順位は次のとおりです。

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

上記の質問では、優先順位関数を検討してください

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

上記の OPERATOR PRECEDENCE TABLE に従って、operator1 の各値について、operator2 の対応する値の優先順位をチェックする必要があります。適切な比較なしで値を返さないでください。