Дерево выражений, дающее неправильный ответ - PullRequest
Новая
       0

Дерево выражений, дающее неправильный ответ

0 голосов
/ 21 апреля 2011

РЕДАКТИРОВАТЬ

Это домашнее задание, поэтому, пожалуйста, не вводите код.Просто намеки, спасибо!

Я работаю над проектом, который будет использовать дерево выражений для получения различных вещей, а затем выполнять операции над ними.Прямо сейчас я не слишком беспокоюсь о производной части, я просто хочу разобрать часть операций.

Код дерева выражений, который я использую, работает для целых чисел, но как только я введу "x" или любой другойдругая переменная мой ответ неверен.Моя программа работает со строками выражений postfix ... ниже приведен пример того, что правильно и неправильно.

5 6 + возвращает 11. правильное

5x 6x + возвращает 11. неверное должно быть11x

Вот мой код: 

// This is the expression tree code I'm using
#ifndef EXPRNODE_H
#define EXPRNODE_H

#include <cstdlib>  // for NULL
using namespace std;

//====================================== class ExprNode
class ExprNode {
 public:
    ExprNode(char oper, ExprNode* left, ExprNode* right);
    ExprNode(int val);
    int eval() const; // Evaluate expr tree. Return result.

 private:
    char      _op;    // one of +, -, *, /, #
    int       _value; // integer value used for constants.
    ExprNode* _left;  // left subtree
    ExprNode* _right; // right subtree
};
#endif

//============================================= ExprNode constructor
// Constructs node for a binary operator.
ExprNode::ExprNode(char oper, ExprNode* left, ExprNode* right) {
    _op    = oper;
    _left  = left;
    _right = right;
}

//============================================== ExprNode constructor
// Constructs a node for an integer constant
ExprNode::ExprNode(int v) {
    _op    = '#';
    _value = v;
    _left  = NULL;
    _right = NULL;
}

//===================================================== ExprNode::eval
int ExprNode::eval() const {
    // Recursively evaluate expression tree and return result.
    int result;
    switch (_op) {
        case '+': 
                result = _left->eval() + _right->eval();
                break;
        case '-': 
                result = _left->eval() - _right->eval();
                break;
        case '*':
                result = _left->eval() * _right->eval();
                break;
        case '/':
                result = _left->eval() / _right->eval();
                break;
        case '#': 
                result = _value;  // an integer constant
                break;
     }
     return result;
}

bool isOperator (char operand)
{
    return operand == '+' || operand == '-' || operand == '*' || operand == '/' || operand == '^';
}

bool isNumber (char potentialNumber)
{
    return potentialNumber >= '0' && potentialNumber <= '9';
}

bool isX (char letter)
{
    return letter == 'x' || letter == 'X';
}

Я не собираюсь включать код, идущий от инфикса к постфиксу, потому что он не нужен (я думаю) ... следующим являетсякод для дерева выражений и вычислений 

// the expression string is the postfix expression I returned previously
void expressionTree(string expression)
{
    string tempNum = "";
    string tempNum2 = "";
    int count = 1;
    int tempNumInt;
    int tempNum2Int;

    // creates a blank total value and blank numbers
    ExprNode* totalVal = new ExprNode('+', new ExprNode(0), new ExprNode(0));
    ExprNode* tNum;
    ExprNode* tNum2;

    // loop through the postfix expression
    for (unsigned int iterator = 0; iterator < expression.length(); iterator++)
    {
        if (isOperator(expression[iterator]))
        {
                    // Don't need to worry about at the moment
            if (expression[iterator] == '^')
            {
                // go to derivative later
            }
            else
            {
                if (count % 2 != 0)
                {
                    // we'll do different derivatives here.... for now just add, subtract, multiply, divide
                    totalVal = new ExprNode(expression[iterator], tNum, tNum2);
                }
                else if (count % 2 == 0 && expression[iterator] == '+' || expression[iterator] == '*')
                {
                    totalVal = new ExprNode(expression[iterator], tNum, totalVal);
                }
                else if (count % 2 == 0 && expression[iterator] == '-' || expression[iterator] == '/')
                {
                    totalVal = new ExprNode(expression[iterator], totalVal, tNum);
                }
            }
            count++;
        }
        if (isNumber(expression[iterator]) && count % 2 != 0)
        {
            tempNum += expression[iterator];
        }
        else if (isNumber(expression[iterator]) && count % 2 == 0)
        {
            tempNum2 += expression[iterator];
        }
        if (expression[iterator] == ' ' && count % 2 != 0)
        {
            tempNumInt = atoi (tempNum.c_str());
            tNum = new ExprNode(tempNumInt);
            tempNum = "";
            count++;
        }
        else if (expression[iterator] == ' ' && count % 2 == 0)
        {
            tempNum2Int = atoi (tempNum2.c_str());
            tNum2 = new ExprNode(tempNum2Int);
            tempNum2 = "";
            count++;
        }
        else if (expression[iterator] == ' ')
        {
            count++;
        }
    }
    cout << totalVal->eval() << endl;
}

Я постараюсь объяснить что-то непонятное.Заранее спасибо.

1 Ответ

1 голос
/ 21 апреля 2011

Я не указываю на точную ошибку, но даю вам совет: int ExprNode :: eval () const не должен возвращать 'int'. Этого недостаточно для обработки переменных результатов, таких как «11x» (это не может быть представлено простым int). Вам нужно будет создать собственную структуру, в которой будут храниться целочисленная часть и переменная часть результата (последняя не обязательна).

...