用C++实现普通表达式转逆波兰表达式

Question

要求如下：

题目描述
普通表达式含四则运算、小括号（多级）、浮点数（正负均有），输出相应的逆波兰表达式

小数点保留6位

输入
第一行为样本个数，

接下来每行为一个普通表达式

输出
每行为对应的逆波兰表达式
样例输入
1
-16871.626820 - ( -4772.327189 - -11864.523087 ) + ( -5951.751518 - -411.157567 ) * ( -68.615986 - -750.686850 ) - -393.790857 - 2085.785638
样例输出
-16871.626820 -4772.327189 -11864.523087 - - -5951.751518 -411.157567 - -68.615986 -750.686850 - * + -393.790857 - 2085.785638 -

下面是我的代码，自己调试了很多组数据都没问题，在OJ平台上报出以下运行错误：
Segmentation fault:段错误，检查是否有数组越界，指针异常，访问到不应该访问的内存区域

#include <sstream>
#include <string>
#include <iostream>
#include <ctype.h>
using namespace std;


int priority(char op)             
{  
    if (op=='+' || op=='-')  
        return 1;  
    if (op=='*' || op=='/')  
        return 2;  
    else  
        return 0;  
}  
int main()
{
    double r[5][50]={0};
    char c[5][50]={'\0'};
    std::string strLine;
    int num,i,k;
    std::cin >> num;
    int *t=new int(num);
    std::getline(std::cin, strLine);
    for (i = 0; i < num; i++)
    {
        int j=0;
        char s[50]={'\0'},e;
        int key=0,top=-1;
        std::getline(std::cin, strLine);
        std::stringstream ss(strLine);
        std::string strItem;
        while (ss >> strItem)
        {
            if (strItem.size()>1||isdigit(strItem[0]))
            {
                r[i][key]=std::stod(strItem);
                key=key+1;                
            }
            else
            {
               e=strItem[0];
               if(e=='('){top=top+1;s[top]='(';}
               else if(e==')')
               {
                   if(top>=0)
                   {
                       while(s[top]!='('&&top>=0)
                      {
                       c[i][key]=s[top];
                       top=top-1;
                       key=key+1;
                       }
                   }
                   if(top>=0)top=top-1;
               }
               else 
               {
                   while(1)
                   {
                       if(top==-1||(top>=0&&s[top]=='(') || (top>=0&&priority(e)>priority(s[top]))){top=top+1;s[top]=e;break;}
                       else {if(top>=0)c[i][key]=s[top];top=top-1;key=key+1;}
                   }
               }                                      
            }
        }
        while(top>=0){c[i][key]=s[top];top=top-1;key=key+1;}
        *(t+i)=key;
    }
    
    for (k = 0; k < num; k++)
        {
            for (i= 0;i<*(t+k); i++)
            {
                if(c[k][i]!='\0')cout<<c[k][i]<<" ";
                else printf("%f ",r[k][i]);    
            }
            cout<<endl;
    }
}

错误出在哪里？谢谢。

Answer 1

既然是越界，请检查你的下标访问。

中缀转后缀。简单的表达式求值。

int symbol_priority(char &c)
{
    if (c == '(')return 0;
    else if (c == '+' || c == '-')return 1;
    else if (c == '*' || c == '/')return 2;
    else if (c == ')')return 3;
    else return -1;
}
//判断优先级
bool is_high(char &c)
{
    if (symbol.empty())return true;
    else if (c == '(')return true;
    else if (symbol_priority(symbol.top())<symbol_priority(c))return true;
    else return false;
}
double calculator::operation(double & a, char c, double b)
{
    if (c == '+')a += b;
    else if (c == '-')a -= b;
    else if (c == '*')a *= b;
    else if (c == '/')
    {
        if (abs(b) <= eps)return false;
        else return a /= b;
    }
    else return false;
    return true;
}
//中缀转后缀
void calculator::do_suffix()
{
    while (!expression.empty())
    {
        std::string str = expression.front();
        expression.pop();
        if (is_symbol(str[0]))
        {
            if (is_high(str[0]))
            {
                if (str[0] == ')')
                {
                    while (symbol.top() != '(')
                    {
                        std::string temp = "";
                        suffix.push(temp+=symbol.top());
                        symbol.pop();
                    }
                    symbol.pop();
                }
                else
                    symbol.push(str[0]);
            }
            else
            {
                while (!symbol.empty())
                {
                    if (is_high(str[0]))
                    {
                        break;
                    }
                    std::string temp = "";
                    suffix.push(temp+=symbol.top());
                    symbol.pop();
                }
                symbol.push(str[0]);
            }
        }
        else
        {
            suffix.push(str);
        }
    }
    while (!symbol.empty())
    {
        std::string temp = "";
        suffix.push(temp += symbol.top());
        symbol.pop();
    }
}
//计算
bool calculator::count()
{
    std::stack<double>number;
    while (!suffix.empty())
    {
        std::string temp = suffix.front();
        suffix.pop();
        if (!is_symbol(temp[0]))
        {
            number.push(atof(temp.c_str()));
        }
        else
        {
            double temp1 = number.top(); number.pop();
            double temp2 = number.top(); number.pop();
            if (!operation(temp2,temp[0],temp1))
            {
                return false;
            }
            else
            {
                number.push(temp2);
            }
        }
    }
    answer = number.top();
    number.pop();
    return true;
}

我的expression是把中缀表达式分割成token装入queue的。

PS：即使是同样是面向OJ编程，我觉得我当年的代码风格比你好多了。