algorithm - Spoj问题ONP Transform the expression giving signal abort

Question

我正在尝试解决 ONP - 转换 spoj 中的表达式。问题是将中缀表达式转换为后缀表达式。我使用 std::stack 作为我的数据结构和调车场算法来解决它。该代码使用 g++ 在我的计算机上运行良好。但是在 spoj 上，它给出了 SIGABRT 错误。即使在 ideone 上，它也会给出运行时错误 free() invalid pointer。

我已经尝试了几个测试用例。起初，我以为我的程序占用了太多内存，但在使用 time -v (ubuntu) 进行测试后，我发现占用的最大空间以 KB 为单位。

// ------------------- infix to postfix conversion ---------------

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#include <utility>

using std::stack;
using std::pair;
using std::cout;
using std::cin;
using std::endl;
using std::string;

stack< pair<char, short> > op_st; // operator stack

short op_precedence(char op) {
    // return operator precedence
    // input: operator; output: its precedence value

    switch (op) {
        case '+': return 0;
        case '-': return 1;
        case '*': return 2;
        case '/': return 3;
        case '^': return 4;
        case '(': return 6; 
    }
}

inline bool is_operator(char sym) {
    // is sym an operator?
    return (sym == '+' || sym == '-' || sym == '*' || sym == '/' || sym == '^' || sym == '(');
}

inline bool is_operand(char sym) {
    // is sym an operand? 
    return (sym >= 'a' && sym <= 'z');
}

void in_to_post(string & expr) {
    // infix to postfix converter
    // input: infix expression


    for (int i = 0; i < expr.length(); ++i) {
        if (is_operator(expr[i])) { // operator
            // pop op_stack until the 
            // top of the stack has less precedence 
            // than curr operator or stack is empty
            while(1) {
                if (op_st.empty()) { // stack is empty; straight away push
                    op_st.push(std::make_pair(expr[i], op_precedence(expr[i])));
                    break;
                }
                pair <char, short> & top_op = op_st.top();
                if (op_precedence(top_op.second) >= op_precedence(expr[i])) {
                    cout << top_op.first;
                    op_st.pop();
                }
                else {
                    op_st.push(std::make_pair(expr[i], op_precedence(expr[i])));
                    break;
                }
            }
        }
        else if (is_operand(expr[i])) { // operand; push it to output queue immediately
            cout << expr[i];
        }
        else if (expr[i] == ')') {  // right paranthesis
            while (1) {
                if (op_st.empty()) { // invalid expression; ')' reached before matching '('
                    //cout << "No matching '(' found\n";
                    abort();
                }
                pair <char, short> & top_op = op_st.top();
                if (top_op.first == '(') { // matching '(' found; stop
                    op_st.pop();
                    break;
                }
                else {
                    cout << top_op.first;
                    op_st.pop();
                }
            }
        }
    }

    // pop out the whole op_st (if any)
    while (!(op_st.empty())) {
        pair <char, short> & top_op = op_st.top();
        cout << top_op.first;
        op_st.pop();
    }
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        string expr;
        cin >> expr;
        //cout << expr.length() << endl;
        in_to_post(expr);
        cout << "\n";
    }
    return 0;
}

我系统上给定程序的输入:

((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))+((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))-((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))*((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))^((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))+((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))^((a+b)-c*(d+e))^((a+b)-c*(d+e))+((a+b)-c*(d+e))-((a+b)-c*(d+e))

成功给出输出:

ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*-ab+cde+*--+^^-+^+-+^^-+^*-+^--+^+-+^.

但是，同样的代码在 ideone 中给出了 free() invalid pointer 错误。这是为什么？

Answer 1

op_precedence(top_op.second) 使用之前 op_precedence 调用返回的数字调用 op_precedence - 而不是使用运算符字符。

当 op_precedence 被传递一个与识别的操作符之一不匹配的参数时，程序表现出未定义的行为，通过到达非 void 的结尾> 在没有遇到 return 语句的情况下运行。