写点什么

表达式转换 - 中缀转后缀表达式后计算 - 数据结构与算法

作者:阿锋
  • 2022 年 8 月 15 日
    湖北
  • 本文字数:2825 字

    阅读完需:约 9 分钟

表达式转换-中缀转后缀表达式后计算-数据结构与算法

前言

🚀 个人主页:阿阿阿阿锋的主页_CSDN🔥 有问题欢迎指出,🔥 希望能和大家一起加油,一起进步!


🌍 另外,给大家推荐一款神器:《牛客网》🌍 无论是面试,还是刷题学习,都非常好用。而且调试在线编程题时,是可以对比测试数据对应的正确输出的。





@[TOC]

问题

一个==计算中缀表达式==的算法题


40分,其余六个测试点都显示"read(ASCII 13)"我的代码现在一直只能过第1、6、7、8这四个测试集,查看测试集显示错误信息:“Wrong Answer.wrong answer On line 1 column 25, read (ASCII 13), expected +.”
复制代码


题目链接表达式转换-洛谷


我查了(ASCII 13)是回车键,但是我又能过四个测试集,为什么输出会有回车键的问题呢?


谁能救救我啊?万分感谢!


下面是我的代码(可能有点乱,抱歉):


/*long long1)输入数字是单个数字2)输入没有负数 */#include<iostream>#include<cstdio>#include<stack>using namespace std;const int max0 = 500;stack<char> s;    //计算后缀表达式用 long long get_num();            //从栈中返回一个整型数字 bool compare_sign(char big, char small);  //比较两个(四则运算符)运算符的优先级 void change(char str[]);          //给新转化出来的后缀表达式 操作数 加分隔符'.'void out_bds(char str[], int i, stack<char> ss);//输出中间产物表达式int main() {  char a[max0]{};      //后缀表达式   int ac(0);        //迭代a  stack<char> sign;    //符号栈  char m[max0]{};      //待处理的中缀表达式  char ch(0);  for(int i = 0; i < max0; ++i){    ch = getchar();    if(ch == '\n') break;    m[i] = ch; }   //--------------------一、中缀表达式转后缀表达式   for(int i = 0; i < max0 && m[i] != '\0'; i++) {    //读取中缀表达式并开始转换     if('0' <= m[i] && m[i] <= '9') {        //遇到操作数,直接加入后缀表达式       a[ac++] = m[i]; }    else if(m[i] != '(' && m[i] != ')') {         while(!sign.empty() && compare_sign(sign.top(), m[i])) {         a[ac++] = sign.top();          //遇到运算符,出栈优先级不小于它的运算符加入表达式,直到栈空或遇到'('        sign.pop(); }      sign.push(m[i]); }              //然后自己入栈     else if(m[i] == '(') {      sign.push(m[i]); }    else if(m[i] == ')') {              //遇到')',出栈加入表达式直到'('       while(sign.top() != '(') {        a[ac++] = sign.top();        sign.pop(); }      sign.pop(); }}  while(!sign.empty()) {    //出栈所有剩余运算符     a[ac++] = sign.top();    sign.pop(); }  change(a);  out_bds(a, 0, s);  //--------------------二、计算后缀表达式   char t(0); ac = 0;      while(true) {    t = a[ac++];          //入栈     if(t == '@') {s.pop();break;}    s.push(t);    if(t == '+' || t == '-' || t == '*' || t == '/' || t == '^') {  //见运算符      s.pop();        //出栈运算符      long long d(0), b(0);  //出栈两个数字为int型      s.pop(); d = get_num();      s.pop(); b = get_num();      long long result(1);  //计算      if(t == '+') result = b + d;      else if(t == '-') result = b - d;      else if(t == '*') result = b * d;      else if(t == '/') result = b / d;      else if(t == '^') {        for(int i = 0; i < d; ++i)          result *= b; }      if(result < 0) {s.push('0'); result = -result;}      stack<char> c;      //结果转为char型再入栈      if(result == 0) {s.push('0');}      while(result != 0) {        c.push((char)(result % 10 + '0'));        result /= 10; }      while(!c.empty()) {        s.push(c.top());        c.pop(); }      s.push('.');      out_bds(a, ac, s); }}  return 0; }//----------------------------------------//只考虑了表达式转换过程中可能发生的优先级比较 bool compare_sign(char big, char small) {  if(big == '+' || big == '-') {    if(small == '+' || small == '-') return true; }  else if(big == '*' || big == '/' || big == '^') {    if(small != '(' && small != '^') return true; }  return false; }//----------------------------------------//从char型栈中读取出一个int型操作数 long long get_num() {  long long sum(0);  char t(0);  for(long long i = 1; s.top() != '.'; i *= 10) {    //i也是必须开long long的     t = s.top();    sum += (long long)(s.top() - '0') * i;    s.pop();    if(s.empty()) break; }  if(t == '0') sum = -sum;  return sum; }//----------------------------------------//从char型栈中读取出一个int型操作数;out_bds()的配套 long long get_num(stack<char> &ss) {  long long sum(0);  char t(0);  for(long long i = 1; ss.top() != '.'; i *= 10)   {  t = ss.top();    sum += (long long)(ss.top() - '0') * i;    ss.pop();    if(ss.empty()) break; }  if(t == '0') sum = -sum;  return sum; }//----------------------------------------//给新转化出来的后缀表达式 操作数 加分隔符'.'void change(char str[]) {  char t[max0]{};  int tc(0);  for(int i = 0; str[i] != '\0'; i++) {    if('0' <= str[i] && str[i] <= '9') {      t[tc++] = str[i];      t[tc++] = '.'; }    else t[tc++] = str[i]; }  for(int i = 0; t[i] != '\0'; i++)     str[i] = t[i];  str[tc] = '@'; }    //表达式结束符//----------------------------------------//输出中间产物表达式,从str[i]开始;参数建立了一个副本栈,不担心原s改变 void out_bds(char str[], int i, stack<char> ss) {  stack<long long> t;      //中转站   while(ss.empty() == 0) {    if(ss.top() == '.')      ss.pop();    t.push(get_num(ss)); }  while(t.empty() == 0) {    cout << t.top() << " ";    t.pop(); }  for( ; str[i] != '\0'; i++) {    if(str[i] != '.' && str[i] != '@')       cout << str[i] << " "; }  cout << endl; } /*测试集8-(3+2*6)/5+49+(9^8+(9^8+(9^8+(9^8))))*/ 
复制代码


程序运行:


经验总结

  • 注意创建的==数组大小==,题目说输入字符串长度不超过 100,但是表达式计算过程中的==中间结果==是可能超过 100 的。

  • 注意不要==变量名冲突==。

  • 仔细审题,有些坑很细,如:计算过程总数字==不超过==2^31^,但是可能等于,那 int 类型就不够了。

  • 如果==重载==了函数,修改其中一个时可能其它的也需要修改

  • 输出==格式==其实挺烦的,有时题目不会说很清楚,甚至就必须有行末空格。

发布于: 刚刚阅读数: 3
用户头像

阿锋

关注

还未添加个人签名 2022.08.09 加入

还未添加个人简介

评论

发布
暂无评论
表达式转换-中缀转后缀表达式后计算-数据结构与算法_算法与数据结构_阿锋_InfoQ写作社区