时间戳

首页 > 解决方案 > 中缀到后缀输出程序

c++ - 中缀到后缀输出程序

问题描述

我是一个新手 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在输出中而不是运算符符号中，而且答案也不同。请帮我解决一下这个。

标签： c++stringstackpostfix-notationinfix-notation

解决方案

首先，我只想指出类的使用是为了隐藏数据。使您的top,size和其他数据成员成为public范围完全违背了目的。其次，类的命名法应该以大写字母开头。

第一个错误与您的stack::Push(char)方法有关。return astack[--top]注意和之间的区别return astack[top--]。前者将 的值减top1，然后返回该值，而后者返回 的值，astack[top]然后递减top。

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

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

此外，由于stack::print(stack *)是类的方法，因此每个实例都有自己的该成员函数的副本。不需要显式地传递一个实例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);
    }
}

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

推荐阅读