使用队列和堆栈的后缀评估 C++

Question

主要代码相关文件将link编辑为github

https://github.com/andrew-chen/csis252/blob/master/examples/token/token.h

https://github.com/andrew-chen/csis252/blob/master/examples/stackType.h

https://github.com/andrew-chen/csis252/blob/master/examples/queueType.h

token.cpp 没有 link 所以我将复制并粘贴到这里

// File:      token.cpp
// This file contains the specification for the token class.  
#include <cmath>
#include <cassert>
#include <cctype>
#include "token.h"
/*
{
      static bool unary; // to identify unary minus
      bool isnumber;     // identify whether it's a number or not
      double value;      // an operand
      char ch;           // an operator or parenthesis
      bool valid;        // true if Token is valid
}
*/
Token::      Token()                         // no argument constructor
{
    valid=false;
};

Token::      Token(double d)                   // double constructor
{
    value = d;
    valid=true;
    isnumber = true;
};
Token::      Token(int i)                      // int constructor
{
    value = i;
    valid = true;
    isnumber = true;
};
Token::      Token(char c)                     // char constructor
{
    ch = c;
    isnumber = false;
    switch (ch) {
        case '(': 
        case ')': 
        case '+': 
        case '-': 
        case '*': 
        case '/': 
        case '%': 
        case '^': 
            valid = true;
            return;
        default:
            valid = false;
    };
};

bool Token::      Valid() const              // true if token is valid
{return valid;};
bool Token::      IsOperand() const          // true if token is an operand
{return isnumber;};
bool Token::      IsOperator() const         // true if token is an operator
{
    switch(ch) {
        case '+':
        case '-':
        case '*':
        case '/':
        case '%':
        case '^':
            return true;
        default:
            return false;
    };
};
bool Token::      IsLeftParen() const        // true if token is a (
{
    return (ch == '(');
};
bool Token::      IsRightParen() const       // true if token is a )
{
    return (ch == ')');
};
double Token::      Operand() const          // returns the value of the operand
{
    return value;
};
char Token::      Operator() const           // returns '+' '-' '*' '/' '%' '^' 
{
    return ch;
};
int Token::      Precedence() const          // returns precedence of operator
{
    switch(ch) {
        case '(': return 0;
        case ')': return 0;
        case '^': return 3;
        case '*': return 2;
        case '/': return 2;
        case '%': return 2;
        case '+': return 1;
        case '-': return 1;
        default: return 0;
    };
};

Token Token::      operator + (const Token & arg) const // add Token to object
{
    return Token(value + arg.value);
};
Token Token::      operator - (const Token& arg) const // subtract Token from object
{
    return Token(value - arg.value);
};
Token Token::      operator * (const Token& arg) const // multiply object by Token
{
    return Token(value * arg.value);
};
Token Token::      operator / (const Token& arg) const // divide object by Token
{
    return Token(value / arg.value);
};
Token Token::      operator % (const Token& arg) const // modulus object by Token
{
    return Token(int(value) % int(arg.value));
};
Token Token::      operator ^ (const Token& arg) const // raise object to power of Token
{
    return Token(pow(value,arg.value));
};
istream& operator >> (istream&i,Token&t) // overload input
{
    char c;
    i.get(c);
    if (isdigit(c)) {
        i.putback(c);
        int v;
        i >> v;
        t = Token(v);
    } else {
        t = Token(c);
    };
    return i;
};
         // A friend function is a none member function that is given access
         // to the private members of a class. Friend functions should be
         // avoided if possible.
         // The >> operator will skip blanks and tabs, not '\n'.
         // '\n' will be read and the token is not valid.
         // This provides a way to have a loop read one line of tokens 
         // then exit when '\n is read.


ostream& operator << (ostream&o,const Token&t) //overload output
{
    assert(t.Valid());
    if (t.IsOperand()) {
        o << t.Operand();
    } else {
        o << t.Operator();
    };
    return o;
};

#include "token.h"
#include "queueType.h"
#include "stackType.h"
#include <iostream>
using namespace std;
int main()
{

    queueType<Token> resultQue;
    stackType<Token> movingStack;
    stackType<Token> newResult;
    queueType<Token> copyresutQue;
    char exponent = '^';
    Token t;
    cout << "enter infix expression: ";
    cin >> t;
    while(t.Valid()){
        if(t.IsOperand()){
            resultQue.addQueue(t);
        }
        else if(t.IsLeftParen()){
            movingStack.push(t);
        }
        else if(t.IsRightParen()){
            while(!movingStack.isEmptyStack()){
                if(movingStack.top().IsOperator()){
                    resultQue.addQueue(movingStack.top());
                    movingStack.pop();

                }
                if(movingStack.top().IsLeftParen()){
                    movingStack.pop();
                    break;
                }


            }
        }
        else if(t.IsOperator()){
            while(!movingStack.isEmptyStack()){
                if(movingStack.top().IsOperator()){
                    if(movingStack.top().Operator()==exponent || t.Precedence()>movingStack.top().Precedence() ||movingStack.top().IsLeftParen() ){
                        break;
                    }
                    resultQue.addQueue(movingStack.top());
                    movingStack.pop();
                }
                else if(movingStack.top().IsLeftParen()){
                    break;
                }
            }
            movingStack.push(t);

        }



        cin >> t;

    }
    while(!movingStack.isEmptyStack()){
        if(movingStack.top().IsOperator()){
            resultQue.addQueue(movingStack.top());
            movingStack.pop();
        }
    }
//    while(!movingStack.isEmptyStack()){
//        cout << movingStack.top() << endl;
//        movingStack.pop();
//    }

    cout << "PostFit Express" <<endl;
    while(!resultQue.isEmptyQueue()){
        cout << resultQue.front()<< " ";
        copyresutQue.addQueue(resultQue.front());
        resultQue.deleteQueue();
    }
    cout << "\ncopy Result"<<endl;
    while(!copyresutQue.isEmptyQueue()) {
        cout << copyresutQue.front()<<endl;
        if (copyresutQue.front().IsOperand()) {
            newResult.push(copyresutQue.front());
            copyresutQue.deleteQueue();
//            cout << copyresutQue.front() <<endl;
        }
        if(copyresutQue.front().IsOperator()){
            Token result;
            while(!newResult.isEmptyStack()){
//                cout << newResult.top()<<endl;
                if(newResult.top().IsOperand()){
                    Token num1 = newResult.top().Operand();
//                    cout << num1 << endl;
                    newResult.pop();
                    Token num2 = newResult.top().Operand();
//                    cout<<num2<<endl;
                    newResult.pop();
                    cout << newResult.top()<<endl;

                    switch (copyresutQue.front().Operator())
                    {
                      case '+' :  result = num2 + num1; break;
                      case '-' :  result = num2 - num1; break;
                      case '*' :  result = num2 * num1; break;
                      case '/' :  result = num2 / num1; break;
                      case '%' :  result = num2 % num1; break;
                      case '^' :  result = num2 ^ num1; break;
                    }
//                    cout<<result<<endl;
                    newResult.push(result);

                }
            }
            copyresutQue.deleteQueue();

        }
//        cout << newResult.top()<<endl;
//        copyresutQue.deleteQueue();


    }

    return 0;
}

到目前为止，我已经能够将中缀转换为后缀表达式，现在我的问题是后缀求值。无论出于何种原因，我的副本 copyresutQue 删除了一些队列，并且不会将它们推送到我的 newResult 堆栈中。由于当 pop() 操作数执行评估的算术部分时，来自 copyresutQue 的队列被删除，它将在我的代码中显示一个空堆栈错误，因为没有任何东西可以从 newResult 堆栈中弹出。

例子：输入 (10+3)-2 中缀表达式 10 3 + 2-

它将添加 10 + 3 并将 13 压入新结果堆栈，但随后会显示错误，因为无论出于何种原因，队列的其余部分都将被删除。此外，其余文件由讲师提供，因此它们应该 100% 正确。对于这项作业，我必须使用队列和堆栈，我知道还有其他方法可以完成这项作业。谢谢你的时间。

Answer 1

最后一个 while 循环有问题。

while(!copyresutQue.isEmptyQueue()) {
    if(copyresutQue.front().IsOperand()) {
        newResult.push(copyresutQue.front());
        copyresutQue.deleteQueue();
    }
    else {
        Token result;
        Token num1 = newResult.top();
        newResult.pop();
        Token num2 = newResult.top();
        newResult.pop();
        auto binaryOperator = copyresutQue.front();
        copyresutQue.deleteQueue();
        cout << binaryOperator << endl;
        switch (binaryOperator.Operator())
        {
          case '+' :  result = num2 + num1; break;
          case '-' :  result = num2 - num1; break;
          case '*' :  result = num2 * num1; break;
          case '/' :  result = num2 / num1; break;
          case '%' :  result = num2 % num1; break;
          case '^' :  result = num2 ^ num1; break;
        }
        newResult.push(result);


    }
}
cout << newResult.top()<<endl;

使用队列和堆栈的后缀评估 C++

postfix evaluation using queues and stacks c++

c++

infix-notation

postfix-notation