pex7_4.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>          // used for function 'isdigit'
#include <math.h>			// used for function pow
#pragma hdrstop

#include "tstack.h"         // include template-based stack class

// list of constants specifying specific error messages  
const int OperatorExpected = 0,
          OperandExpected = 1,
          MissingLeftParenthesis = 2,
          MissingRightParenthesis = 3,
          InvalidInput = 4;
          
// labels designating the parentheses characters 
const char leftparenthesis  = '(',
           rightparenthesis = ')';

// a class that handles operators on the operator stack
class MathOperator
{
    private:
        // operator and its two precedence values
        char op;
        int inputprecedence;
        int stackprecedence;
        
    public:
        // constructors; includes default constructor and a 
        // constructor that initializes the object
        MathOperator(void);
        MathOperator(char ch);
        
        // member functions handling operator on the stack
        int operator>= (MathOperator a) const;
        void Evaluate (Stack<float> &OperandStack);
        char GetOp(void);
};

// default constructor
MathOperator::MathOperator(void)
{}

// constructor that assigns operator and precedences values
MathOperator::MathOperator(char ch)
{
    op = ch;    // assign operator
    switch(op)
    {
        // '+' and '-' have input/stack precedence 1
        case '+':   
        case '-':   inputprecedence = 1;
                    stackprecedence = 1;
                    break;
                                
        // '*' and '/' have input/stack precedence 2
        case '*':   
        case '/':   inputprecedence = 2;
                    stackprecedence = 2;
                    break;
                            
        // '^' has input precedence 4 and stack precedence 3.
        // done so the operator is right associative
        case '^':   inputprecedence = 4;
                    stackprecedence = 3;
                    break;
                            
        // '(' has input precendence 3, stack precedence -1
        case '(':   inputprecedence = 3;
                    stackprecedence = -1;
                    break;
                            
        // ')' has input/stack precedence 0
        case ')':   inputprecedence = 0;
                    stackprecedence = 0;
                    break;
    }
}
        
// overload the >= operator by comparing stackprecedence of
// the current object with inputprecedence of a. used when
// reading an operator to determine whether operators
// on the stack should be evaluated before pushing the new
// operator on the stack. 
int MathOperator::operator>= (MathOperator a) const
{
    return stackprecedence >= a.inputprecedence;
}
        
// evaluate operator for the current object. First pop two
// operands from the operand stack, then execute operator and
// push the result back onto the operand stack.   
void MathOperator::Evaluate (Stack<float> &OperandStack)
{
    float operand1 = OperandStack.Pop(); // get right operand
    float operand2 = OperandStack.Pop(); // get left operand
            
    // evaluate operator and push result back on the stack
    switch (op)                          // select operation
    {
        case '+' :  OperandStack.Push(operand2 + operand1);
                    break;
                            
        case '-':   OperandStack.Push(operand2 - operand1);
                    break;
                            
        case '*':   OperandStack.Push(operand2 * operand1);
                    break;
                
        case '/':   OperandStack.Push(operand2 / operand1);
                    break;
                    
        case '^':   OperandStack.Push(pow(operand2,operand1));
                    break;
    }
}

// return operator associated with current object        
char MathOperator::GetOp(void)
{
    return op;
}

// checks if character is an operator or parentheses
int isoperator(char ch)
{
    if (ch == '+' || ch == '-' || ch == '*' ||
    	ch == '/' || ch == '^' || ch == '(')
		return 1;
    else
        return 0;
}

// checks if character is a whitespace character
int iswhitespace(char ch)
{
    if (ch == ' ' || ch == '\t' || ch == '\n')
		return 1;
    else
        return 0;
}

// error handling function
void error(int n)
{
    // table gives the different error messages
    static char *errormsgs[] = {
                    "Operator expected",
                    "Operand expected",
                    "Missing left parenthesis",
                    "Missing right parenthesis",
                    "Invalid input"
                };
                        
    // the parameter n is an error message index
    // print the message and terminate the program  
    cerr << errormsgs[n] << endl;
    exit(1);
}

void main(void)
{
    // declaration of operator stack with MathOperator objects
    Stack<MathOperator> OperatorStack;
    
    // declaration of the operand stack. 
    Stack<float> OperandStack;
    
    MathOperator opr1,opr2;
    int rank = 0;
    float number;
    char ch;

    // process the expression until '=' is read
    while (cin.get(ch) &&  ch != '=')
    {
        //  ********  process a floating point operand  ********
        if (isdigit(ch) || ch == '.')
        {
            // put back digit or '.' and read number
            cin.putback(ch);
            cin >> number;
            // rank of operand is 1. accumulated rank must be 1
            rank++;
            if (rank > 1)
                error(OperatorExpected);
            // push the operand on the operand stack
            OperandStack.Push(number);
        }
        //  *********  process an operator  **********
        else if (isoperator(ch))
        {
            // rank of each operator other than '(' is -1.
            // accumulated rank should be 0
            if (ch != '(')  // rank of '(' is 0
                rank--;
            if (rank < 0)
                error(OperandExpected);
                
            // build a MathOperator object holding current
            // operator. pop the operator stack and evaluate
            // as long as the operator on the top of the stack
            // has a precedence >= that of the current operator.
            // push the current operator on the operator stack
            opr1 = MathOperator(ch);
            while(!OperatorStack.StackEmpty() &&
                  (opr2 = OperatorStack.Peek()) >= opr1)
            {
                opr2 = OperatorStack.Pop();
                opr2.Evaluate(OperandStack);
            }
            OperatorStack.Push(opr1);
        }
        //  *********  process a right parenthesis  **********
        else if (ch == rightparenthesis)
        {
            // build a MathOperator object holding ')', which
            // has precedence lower than the stack precedence
            // of any operator except '('. pop the operator stack
            // and evaluate the subexpression until '(' surfaces 
            // or the stack is empty. if the stack is empty, a
            // '(' is missing; otherwise, delete '('.
            opr1 = MathOperator(ch);
            while(!OperatorStack.StackEmpty() &&
                  (opr2 = OperatorStack.Peek()) >= opr1)
            {
                opr2 = OperatorStack.Pop();
                opr2.Evaluate(OperandStack);
            }
            if(OperatorStack.StackEmpty())
                error(MissingLeftParenthesis);
            opr2 = OperatorStack.Pop(); // get rid of '('
        }   
        //  *********  have some invalid input  **********
        else if (!iswhitespace(ch))
            error(InvalidInput);
    }
    
    // the rank of the complete expression must be 1
    if (rank != 1)
        error(OperandExpected);
    
    
    // flush operator stack and complete expression evaluation.
    // if find left parenthesis, a right parenthesis is missing.
    while (!OperatorStack.StackEmpty())     
    {
        opr1 = OperatorStack.Pop();
        if (opr1.GetOp() == leftparenthesis)
            error(MissingRightParenthesis);
        opr1.Evaluate(OperandStack);
    }
    

    // value of the expression is on the top of the operand stack
    cout << "The value is " << OperandStack.Pop() << endl;
}
                
/*
<Run>

2 ^ 2 ^ 3 =
The value is 256
*/