0

我刚刚将中缀转换为后缀并用一位数字进行计算，但我无法转换为后缀并用 N 位进行计算。可能有人帮我解决这个问题！非常感谢 ：-）

这是我的个位数代码

字符堆栈.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);

整数堆栈.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);

波兰符号.h

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

字符堆栈.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;
    }
}

整数堆栈.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;
    }

模板堆栈.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;
    }
}

主文件

#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 回答