0

インフィックスをポストフィックスに変換して 1 桁で計算しましたが、ポストフィックスに変換して N 桁で計算できません。誰かがこれで私を助けてくれるかもしれません! どうもありがとう ：-）

ここに1桁の私のコードがあります

CharacterStack.h

#define MAX 100
typedef struct
{
    int top;
    char a[MAX];
} CHARACTER_STACK;

void Initialize(CHARACTER_STACK &stack);
bool IsEmpty(CHARACTER_STACK stack);
bool IsFull(CHARACTER_STACK stack);
bool Push(CHARACTER_STACK &stack, char x);
char Pop(CHARACTER_STACK &stack);
char GetTop(CHARACTER_STACK stack);
void Display(CHARACTER_STACK stack);

IntegerStack.h

#define MAX 100
typedef struct
{
    int top;
    int a[MAX];
} INTEGER_STACK;

void Initialize(INTEGER_STACK &stack);
bool IsEmpty(INTEGER_STACK stack);
bool IsFull(INTEGER_STACK stack);
bool Push(INTEGER_STACK &stack, int x);
int Pop(INTEGER_STACK &stack);
int GetTop(INTEGER_STACK stack);
void Display(INTEGER_STACK stack);

PolishNotation.h

#include "string"
using namespace std;
string Infix2Postfix(string infix);
int CalcPostfix(string postfix);

CharacterStack.cpp

#include "CharacterStack.h"
#include "iostream"
using namespace std;


void Initialize(CHARACTER_STACK &stack)
{
    stack.top = 0;
}

bool IsEmpty(CHARACTER_STACK stack)
{
    if (stack.top == 0)
        return true;
    return false;
}

bool IsFull(CHARACTER_STACK stack)
{
    if (stack.top == MAX)
        return true;
    return false;
}

bool Push(CHARACTER_STACK &stack, char x)
{
    if ( !IsFull(stack) )
    {
        stack.a[stack.top] = x;
        stack.top++;
        return true;
    }
    return false;
}

char Pop(CHARACTER_STACK &stack)
{
    if ( !IsEmpty(stack) )
    {
        stack.top--;
        return stack.a[stack.top];
    }
    return NULL;
}

char GetTop(CHARACTER_STACK stack)
{
    if ( !IsEmpty(stack) )
    {
        return stack.a[stack.top-1];
    }
    return NULL;
}

void Display(CHARACTER_STACK stack)
{
    cout << "Stack characters: ";
    if ( !IsEmpty(stack) )
    {
        for (int i = stack.top - 1; i >= 0; i--)
            cout << stack.a[i] << " ";
        cout << endl;
    }
    else
    {
        cout << "is EMPTY !!!" << endl;
    }
}

IntegerStack.cpp

#include "IntegerStack.h"
#include "iostream"
using namespace std;


void Initialize(INTEGER_STACK &stack)
{
    stack.top = 0;
}

bool IsEmpty(INTEGER_STACK stack)
{
    if (stack.top == 0)
        return true;
    return false;
}

bool IsFull(INTEGER_STACK stack)
{
    if (stack.top == MAX)
        return true;
    return false;
}

bool Push(INTEGER_STACK &stack, int x)
{
    if ( !IsFull(stack) )
    {
        stack.a[stack.top] = x;
        stack.top++;
        return true;
    }
    return false;
}

int Pop(INTEGER_STACK &stack)
{
    if ( !IsEmpty(stack) )
    {
        stack.top--;
        return stack.a[stack.top];
    }
    return NULL;
}

int GetTop(INTEGER_STACK stack)
{
    if ( !IsEmpty(stack) )
    {
        return stack.a[stack.top-1];
    }
    return NULL;
}

void Display(INTEGER_STACK stack)
{
    cout << "Stack integers: ";
    if ( !IsEmpty(stack) )
    {
        for (int i = stack.top - 1; i >= 0; i--)
            cout << stack.a[i] << " ";
        cout << endl;
    }
    else
    {
        cout << "is EMPTY !!!" << endl;
    }
}

ポーランド記法.cpp

 #include "string"
    #include "limits"
    using namespace std;
    #include "CharacterStack.h"
    #include "IntegerStack.h"
    #include "TemplateStack.cpp"
    #include "stack"

    int Precedence(char operatorr)
    {
        if (operatorr == '+' || operatorr == '-') return 1;
        if (operatorr == '/' || operatorr == '*' || operatorr == '%') return 2;
        return 0;
    }

    bool IsOperand(char operand)
    {
        if (operand >= '0' && operand <= '9')
            return true;
        return false;
    }

    string Infix2Postfix(string infix)
    {
        string postfix = "";

        //CHARACTER_STACK stack;
        STACK<char> stack; // using template
        Initialize(stack);
        string temp;
        //char ch;
        // step 1
        for (int i = 0 ; i < infix.length(); i++)
        {
            char item = infix[i];
            //
            if (IsOperand(item)) // step 1.1
                postfix += item;
            else if (item == '(') // step 1.2
                Push(stack, item);
            else if (item == ')') // step 1.3
            {
                char x;
                while ( (x = Pop(stack)) != '(' )
                    postfix += x;
            }
            else // step 1.4
            {
                while ( !IsEmpty(stack) && Precedence(GetTop(stack)) >= Precedence(item) )
                {
                    postfix += Pop(stack);
                }
                Push(stack, item);
            }
            //Display(stack); // for DEBUG
        }
        // step 2
        char x;
        while ( (x = Pop(stack)) != NULL )
            postfix += x;

        return postfix;
    }

    int CalcPostfix(string postfix)
    {
        int result = 0;

        //INTEGER_STACK stack;
        STACK<int> stack; // using template
        Initialize(stack);

        // step 1
        for (int i = 0 ; i < postfix.length(); i++)
        {
            char item = postfix[i];

            if (IsOperand(item)) // step 1.1
            {
                int x = item - '0';
                Push(stack, x);
            }
            else // step 1.2
            {
                int x = Pop(stack);
                int y = Pop(stack);

                int z = numeric_limits<int>::min(); // minimum value
                if (item == '+') z = y + x;
                else if (item == '-') z = y - x;
                else if (item == '*') z = y * x;
                else if (item == '/') z = y / x;
                else if (item == '%') z = y % x;
                Push(stack, z);
            }
            //Display(stack); // for DEBUG
        }
        // step 2
        result = GetTop(stack);

        return result;
    }

TemplateStack.cpp

#include "iostream"
using namespace std;


#define MAX 100

template<class T>
struct STACK
{
    int top;
    T a[MAX];
};

template<class T>
void Initialize(STACK<T> &stack)
{
    stack.top = 0;
}

template<class T>
bool IsEmpty(STACK<T> stack)
{
    if (stack.top == 0)
        return true;
    return false;
}

template<class T>
bool IsFull(STACK<T> stack)
{
    if (stack.top == MAX)
        return true;
    return false;
}

template<class T>
bool Push(STACK<T> &stack, T x)
{
    if ( !IsFull(stack) )
    {
        stack.a[stack.top] = x;
        stack.top++;
        return true;
    }
    return false;
}

template<class T>
T Pop(STACK<T> &stack)
{
    if ( !IsEmpty(stack) )
    {
        stack.top--;
        return stack.a[stack.top];
    }
    return NULL;
}

template<class T>
T GetTop(STACK<T> stack)
{
    if ( !IsEmpty(stack) )
    {
        return stack.a[stack.top-1];
    }
    return NULL;
}

template<class T>
void Display(STACK<T> stack)
{
    cout << "Stack members: ";
    if ( !IsEmpty(stack) )
    {
        for (int i = stack.top - 1; i >= 0; i--)
            cout << stack.a[i] << " ";
        cout << endl;
    }
    else
    {
        cout << "is EMPTY !!!" << endl;
    }
}

main.cpp

#include "PolishNotation.h"
#include "string"
#include "iostream"
using namespace std;
  void main()
    {
        string infix ;
        cout<<"insert infix ";
        cin>>infix;
        cout << "infix = " << infix << endl;

        string postfix = Infix2Postfix(infix);
        cout << "postfix = " << postfix << endl;

        int result = CalcPostfix(postfix);
        cout << "result = " << result << endl;
    }
4

1 に答える 1

0

以下の IsOperand のチェックで:

    if (IsOperand(item)) // step 1.1
    {
        int x = item - '0';
        Push(stack, x);
    }

それが数字であることを確認したら、できるだけ多くのことを読みたいと思うでしょう:

if (IsOperand(item)) // step 1.1
{
  int x;
  sscanf(infix.c_str()+i,"%d",&x); // read x in
  Push(stack, x);
  while ( i+1 < infix.length() // guard to stop reading past end of string
     && IsOperand(infix[i+1]) ) i++; // increment i until integer read completely
}

上記は、複数桁の整数をサポートするようにコードを変更するためのおそらく最も簡単で最短の方法です (コーディングに関して)。

必ず#include <cstdio>sscanf を使用してください。

また、スペースの場合は、次の場所で:

    // step 1
    for (int i = 0 ; i < postfix.length(); i++)
    {
        char item = postfix[i];

に変更します

    while (postfix[i]==' ') i++; // get rid of spaces
    // step 1
    for (int i = 0 ; i < postfix.length(); i++)
    {
        char item = postfix[i];

        .... // other code in for loop

        while (postfix[i]==' ') i++; // get rid of spaces
    }
于 2012-08-19T11:20:24.620 に答える