Spoj问题ONP转换给出信号中止的表达式

Question

我正在尝试解决ONP-转换spoj中的表达式。问题是将中缀表达式转换为后缀表达式。我使用std :: stack作为我的数据结构和调车场算法来解决它。使用g ++在我的计算机上代码可以正常运行。但是在spoj上，它会给出SIGABRT错误。即使在ideone上，它也会给出运行时错误free（）无效指针。

我已经尝试了几个测试用例。起初，我以为我的程序占用了太多内存，但是在使用时间-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（）无效的指针错误。为什么会这样？

Answer 1

[op_precedence(top_op.second)用先前的op_precedence调用返回的号码呼叫op_precedence-而不是操作符。

[当传递op_precedence的参数与公认的运算符之一不匹配时，程序通过到达非void函数的结尾而不会遇到return语句，从而表现出未定义的行为。] >