Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Для новичков > Оценка постфиксного выражения


Автор: qwerty233 3.5.2011, 12:34
Написал программу для оценки постфиксных выражений для одноразрядных чисел, а теперь надо написать для многоразрядных чисел усовершенствовав эту программу, может кто посоветует как это сделать, а то на ум ничего не приходит.
Код

#ifndef STACK_H
#define STACK_H

#include <string>
#include <iostream>

template< typename STACKTYPE > class Stack;

template< typename STACKTYPE >
class StackNode
{
    friend class Stack< STACKTYPE >;
public:
    StackNode( const char &str )
        :nextPtr( 0 ), data( str )
    {}
private:
    StackNode< STACKTYPE > *nextPtr;
    STACKTYPE data;
};

template< typename STACKTYPE >
class Stack
{
public:
    Stack()
        :firstPtr( 0 ), lastPtr( 0 )
    {}

    ~Stack()
    {
        StackNode< STACKTYPE > *currentPtr = firstPtr;
        StackNode< STACKTYPE > *tempPtr;

        while( currentPtr != 0 )
        {
            tempPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
            delete tempPtr;
        }
    }

    void push( const STACKTYPE &pushString )
    {
        StackNode< STACKTYPE > *newPtr = getNewStackNode( pushString );

        if( isEmpty() )
            firstPtr = lastPtr = newPtr;
        else
        {
            newPtr->nextPtr = firstPtr;
            firstPtr = newPtr;
        }
    }

    void pop()
    {
        if( firstPtr == lastPtr )
            firstPtr = lastPtr = 0;
        else
        {
            StackNode< STACKTYPE > *tempPtr = firstPtr;
            firstPtr = firstPtr->nextPtr;
            delete tempPtr;
        }
    }

    bool isEmpty() const
    {
        return firstPtr == 0;
    }

    STACKTYPE stackTop() const
    {
        return firstPtr->data;
    }

    void print() const
    {
        StackNode< STACKTYPE > *printPtr = firstPtr;

        while( printPtr != 0 )
        {
            std::cout << printPtr->data << ' ';
            printPtr = printPtr->nextPtr;
        }
    }
private:
    StackNode< STACKTYPE > *getNewStackNode( const STACKTYPE &newData )
    {
        return new StackNode< STACKTYPE >( newData );
    }
    StackNode< STACKTYPE > *firstPtr;
    StackNode< STACKTYPE > *lastPtr;
};

#endif

Код

#include <iostream>
#include <cmath>
#include <string>
#include "Stack.h"

bool isOperator( const char & );
bool isDigit( const char & );
int evaluatePostfixExpression( Stack< int > &, std::string & );
int calculate( const int &, const char &, const int & );

int main()
{
    Stack< int > stack;
    std::string postfix;

    std::cout << "Enter a postfix expression: ";
    std::getline( std::cin, postfix );

    int answer = evaluatePostfixExpression( stack, postfix );

    std::cout << "Answer is: " << answer << std::endl;
    return 0;
}

bool isOperator( const char &symbolToCheck )
{
    std::string operators( "+-*/^%" );

    for( size_t i = 0; i < operators.length() ; i++ )
        if( symbolToCheck == operators.at( i ) )
            return true;

    return false;
}

bool isDigit( const char &digit )
{
    std::string digits( "0123456789" );

    for( size_t i = 0; i < digits.length(); i++ )
        if( digit == digits.at( i ) )
            return true;
    return false;
}

int calculate( const int &op1, const char &op, const int &op2 )
{    
    int result;
    switch( op )
    {
    case '*': result = op1 * op2;        break;
    case '/': result = op2 / op1;        break;
    case '%': result = op2 % op1;        break;
    case '+': result = op1 + op2;        break;
    case '-': result = op2 - op1;        break;
    case '^': result = pow( static_cast< double >( op2 ), op1 );  break;
    }
    return result;
}

int evaluatePostfixExpression( Stack< int > &s, std::string &postfix )
{
    size_t i = 0;
    int x;
    int y;

    while( i < postfix.length() )
    {
        if( isDigit( postfix.at( i ) ) )
            s.push( static_cast< int >( postfix.at( i ) ) - static_cast< int >( '0' ) );
        else if( isOperator( postfix.at( i ) ) )
        {
            x = s.stackTop();
            s.pop();
            y = s.stackTop();
            s.pop();
            s.push( calculate( x, postfix.at( i ), y ) );
        }
        i++;
        s.print();
    }
    return s.stackTop();
}

Автор: xvr 3.5.2011, 20:32
Цитата(qwerty233 @  3.5.2011,  12:34 Найти цитируемый пост)
Написал программу для оценки постфиксных выражений для одноразрядных чисел, 

 smile 
К хирургу на прием вбегает взъерошенный молодой человек, и с порога требует - Доктор, кастрируйте меня!
- Ну зачем же так, молодой человек, у вас еще вся жизнь впереди ...
- Мне срочно надо!
Ну надо, так надо. Отрезал доктор все, что просили. После операции спрашивает -
- А, если не секрет, зачем?
- Понимаете доктор, я решил женится, а невеста из ортодоксальной еврейской семьи...
- Но у них же делают обрезание!
- А что, я как то неправильно сформулировал???

Может вы все же хотели вычислять постфиксные выражения?

Цитата(qwerty233 @  3.5.2011,  12:34 Найти цитируемый пост)
а теперь надо написать для многоразрядных чисел усовершенствовав эту программу, может кто посоветует как это сделать,

Обратится к тому, кто эту программу писал. Я не верю, что человек написавший это, не в состоянии сделать обработку многоразрядных чисел  smile 

Подсказка - обработка чисел делается в строке 69-70 вашего С++ файла. Откусывайте от входной строки не по 1 цифре, а все (пока они цифры). Что накусаете - и будет числом

Автор: qwerty233 4.5.2011, 14:55
Если вы не верите что это писал я то это ваши проблемы, но мне действительно не приходит в голову как это сделать и кстати в книге было слово "оценка", а не "вычисление"

Автор: xvr 4.5.2011, 15:45
Цитата(qwerty233 @  4.5.2011,  14:55 Найти цитируемый пост)
 книге было слово "оценка", а не "вычисление"

Книгу - 'ф топку'!

Цитата(qwerty233 @  4.5.2011,  14:55 Найти цитируемый пост)
но мне действительно не приходит в голову как это сделать

Зато сделано много велосипедов, так было нужно, или это по незнанию?

Вот ваша обработка (без велосипедов)
Код

#include <iostream>
#include <cmath>
#include <string>
#include <stack>
#include <ctype.h>
#include <string.h>

int evaluatePostfixExpression( std::stack< int > &, std::string & );

int main()
{
    std::stack< int > stack;
    std::string postfix;
    std::cout << "Enter a postfix expression: ";
    std::getline( std::cin, postfix );
    int answer = evaluatePostfixExpression( stack, postfix );
    std::cout << "Answer is: " << answer << std::endl;
    return 0;
}

inline bool isOperator( const char symbolToCheck )
{
  return strchr("+-*/^%",symbolToCheck) != NULL;
}

int calculate( const int &op1, const char &op, const int &op2 )
{    
    int result;
    switch( op )
    {
    case '*': result = op1 * op2;        break;
    case '/': result = op2 / op1;        break;
    case '%': result = op2 % op1;        break;
    case '+': result = op1 + op2;        break;
    case '-': result = op2 - op1;        break;
    case '^': result = pow( static_cast< double >( op2 ), op1 );  break;
    }
    return result;
}

int evaluatePostfixExpression( std::stack< int > &s, std::string &postfix )
{
    size_t i = 0;
    int x;
    int y;
    while( i < postfix.length() )
    {
        if( isdigit( postfix.at( i ) ) )
         {
          const char* p=postfix.c_str();
          char* e;
          s.push( strtoul(p+i,&e,10) );
          i=e-p-1;
         }
        else if( isOperator( postfix.at( i ) ) )
        {
            x = s.top();
            s.pop();
            y = s.top();
            s.pop();
            s.push( calculate( x, postfix.at( i ), y ) );
        }
        i++;
        s.print();
    }
    return s.top();
}

Автор: qwerty233 4.5.2011, 16:12
Цитата

Зато сделано много велосипедов, так было нужно, или это по незнанию?

По незнанию

Автор: borisbn 4.5.2011, 16:55
а зачем в ф-цию evaluatePostfixExpression передаётся объект stack, созданный в main и который потом не используется ? Не проще объявить его локально в функции, если так уж хочется им пользоваться ?
Ещё. А если в строке только одно число или вообще ни одного, то что будет с 
Цитата

y = s.top();

?

Автор: qwerty233 4.5.2011, 17:47
Цитата

а зачем в ф-цию evaluatePostfixExpression передаётся объект stack, созданный в main и который потом не используется ?

А это у меня привычка такая создавать объекты в main()
Цитата

 А если в строке только одно число или вообще ни одного

Этого я не учёл

Автор: qwerty233 4.5.2011, 18:24
Главная проблема в том как объяснить программе при вводе например 681+ что тут 6 + 81 или 68 + 1

Автор: borisbn 4.5.2011, 18:34
Цитата(qwerty233 @  4.5.2011,  17:47 Найти цитируемый пост)
А это у меня привычка такая создавать объекты в main()

почему ж тогда
Цитата(xvr @  4.5.2011,  15:45 Найти цитируемый пост)

size_t i = 0;
int x;
int y;

не в main объявлены, а локально в ф-ции ? smile

Цитата(qwerty233 @  4.5.2011,  18:24 Найти цитируемый пост)
Главная проблема в том как объяснить программе при вводе например 681+ что тут 6 + 81 или 68 + 1

вообще никак. нужно вводить 68 1+ или 68,1+

Автор: qwerty233 4.5.2011, 19:38
Цитата

вообще никак. нужно вводить 68 1+ или 68,1+

Тогда проблема решена

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)