后缀输出程序的中缀

Question

我是一名新手 C++ 程序员。我已经编写了以下 C++ 代码，用于使用基于数组的堆栈表达后缀的中缀，但是，我每次都在字符串中得到 ^2，而且我无法弄清楚为什么我的答案不正确。

我也找不到逻辑错误。有人可以帮我解决这个问题吗？

#include<iostream>
#include <string>

using namespace std;
using std::string;

class stack {
public:
    int top;
    char* astack;
    int size;
    stack(int s) {
        size = s;
        top = -1;
        astack = new char[size];
    }
    void Push(char element);
    char Pop();
    bool isEmpty();
    bool isFull();
    char Peek();
    void clear();
    void print(stack* ptr);
};

char stack::Peek() {
    if (isEmpty()) {
        return 0;
    }
    return astack[top];
}

void stack::clear() {
    top = -1;
    delete astack;
    astack = new char(size);
};

void stack::Push(char element) {
    if (isFull()) {
        cout << "The stack is already Full" << endl;
        return;
    }
    else
        astack[++top] = element;
    return;
}

char stack::Pop() {
    if (isEmpty()) {
        cout << "The Array is already empty" << endl;
    }
    else {
        return astack[--top];
    }
}

void stack::print(stack* ptr) {
    for (int i = 0; i < ptr->top; i++) {
        cout << ptr->astack[i];
    }
}

bool stack::isEmpty() {
    if (top == -1) {
        return 1;
    }
    return 0;
}

bool stack::isFull() {
    if (top == size - 1) {
        return 1;
    }
    return 0;
}

int precedence(char element) {
    int weight = -1;
    switch (element) {
    case '+':
    case '-':
        weight = 1;
    case '*':
    case '/':
        weight = 2;
    case '$':
        weight = 3;
    }
    return weight;
}

bool IsOperator(char C) {
    if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
        return true;
    return false;
}

bool IsOperand(char C) {
    if (C >= '0' && C <= '9') return true;
    if (C >= 'a' && C <= 'z') return true;
    if (C >= 'A' && C <= 'Z') return true;
    return false;
}

int main() {
    string infix;
    getline(cin, infix);

    int j = 1;

    string post = "";

    stack* postfix = new stack(50);
    for (int i = 0; i != infix.size(); i++) {
        char element = infix[i];
        if (IsOperand(element)) {
            post += element;
        }
        if (IsOperator(element)) {
            if (precedence(element) >precedence(postfix->Peek())) {
                postfix->Push(element);
            }
            else {
                while (precedence(element) <= precedence(postfix->Peek())) {
                    if (precedence(element) < precedence(postfix->Peek())) {
                        post += postfix->Pop();
                    }
                    if (precedence(element) == precedence(postfix->Peek())) {
                        cout << postfix->Peek() << endl;
                        post += postfix->Pop();
                    }
                }
            }
        }
    }

    while (!postfix->isEmpty()) {
        post += postfix->Pop();
    }

    cout <<"Postfix expression is : "<< post;
}

输出附在下面：

预期输出：576/1*-6+

我不明白为什么它在输出中有 ^2 而不是运算符符号，而且答案也不同。请帮我解决这个问题。

Answer 1

首先，我只想指出 classes 的使用是为了数据隐藏。让 top、size 和 public 作用域的其他数据成员完全违背了目的。其次，classes的命名应以大写字母开头。

第一个错误是您的 stack::Push(char) 方法。注意 return astack[--top] 和 return astack[top--] 之间的区别。前者将top的值减1，然后return减1，而后者return将astack[top]的值减1，然后减top.

这非常关键，因为您真正想要的是 return 弹出的值，而不是弹出后堆栈顶部的值。

char stack::Pop() {
    if (isEmpty()) {
        cout << "The Array is already empty" << endl;
    }
    else {
        // Note the change here.
        return astack[top--];
    }
}

此外，由于stack::print(stack *)是class的一个方法，每个实例都有自己的成员函数副本。无需显式传递 stack 的实例给它。您可以通过以下代码实现：

void stack::print() {
    for (int i = 0; i <= top; ++i) {
        cout << astack[i];
    }
    
    cout << "\n";
}

转到您的 precedence(char) 函数，您需要在达到目标时跳出切换条件。

int precedence(char element) {
    switch (element) {
        
        case '+': return 1;
        case '-': return 1;
        case '*': return 2;
        case '/': return 2;
        case '$': return 3;
        
        default: return -1;
    }
}

转到将中缀转换为后缀的算法，您必须不断从堆栈中弹出所有相同或更高优先级的运算符，然后压入扫描到的运算符。

if (IsOperand(element)) {
    post += element;
}
else if (IsOperator(element)) {
    if (precedence(element) > precedence(postfix->Peek())) {
        postfix->Push(element);
    }
    else {
        while (precedence(element) <= precedence(postfix->Peek())) {
            post += postfix->Pop();
        }
        
        postfix->Push(element);
    }
}

我建议进行一些更改，例如添加以检查括号，但这似乎超出了这个问题的范围。祝你好运！

后缀输出程序的中缀

Infix to Postfix Output program

c++

string

stack

postfix-notation

infix-notation