学习总结第二十八天——中序表达式补全

不知不觉又咸了几天(嗯),在鸽的这段时间里，参加了下学校的比赛，居然还获得了不错的成绩，但也让我进一步加强了对于自己算法基础差的认识。(接下来要好好补补了)

今天做的事情，就是完成了《算法4》上的关于中序表达式补全问题，其实这个问题本身并不难，但由于java可以很方便的创建字符串栈，用c语言创建的就没有这么方便。最后想到再用两个栈，一个栈保存字符串长度，另外一个保存字符的方法来实现与字符串栈同样的效果。下面为代码：

#include <string.h>
#include <stdbool.h>
#include "stacklib.h"
#ifndef INPUT_LENGTH_MAX
#define INPUT_LENGTH_MAX 100
#endif
int main(int argc, char const *argv[]) {
  char str[INPUT_LENGTH_MAX+1];
  bool last_is_num = false;
  fgets (str,INPUT_LENGTH_MAX,stdin);
  str[strlen(str)-1] = '\0';
  stack *str_len_sta = StackCreate ();
  stack *data_sta = StackCreate();
  stack *opt_sta = StackCreate();
  for (int i=0;i<strlen(str);i++)
  {
    switch (str[i]) {
      case '+':
      case '-':
      case '*':
      case '/':
      case '%':
        StackPush(opt_sta,str[i]);
        last_is_num = false;
      break;
      case ')':
      {
        //分别获取之前串的存储长度
        int b_chars_len = StackPop(str_len_sta);
        int a_chars_len = StackPop(str_len_sta);
        //合计字符串长度，3为一对括号和操作符
        int total_len = a_chars_len + b_chars_len + 3;
        //创建数组并保存上两次的串
        char datas[total_len+1];
        datas[0] = '(';
        datas[total_len]='\0';
        for (int i=total_len-2;i>=2+a_chars_len;i--)//由于是栈，所以从后往前读取
        {
          datas[i] = StackPop(data_sta);
        }
        datas[a_chars_len+1] = StackPop(opt_sta);//取出操作符
        for (int i=a_chars_len;i>0;i--)
        {
          datas[i] = StackPop(data_sta);
        }
        datas[total_len-1] = ')';
        datas[total_len] = '\0';
        //重新存入栈中
        for (int i=0;i<total_len;i++)
        {
          StackPush(data_sta, datas[i]);
        }
        StackPush(str_len_sta,total_len);
        last_is_num = false;
      }
      break;
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
      {
        if (last_is_num==true)
        {
          int temp = StackPop(str_len_sta);
          temp++;
          StackPush(str_len_sta,temp);
          StackPush(data_sta,str[i]);
        }
        else
        {
          StackPush(str_len_sta,1);
          StackPush(data_sta,str[i]);
        }
        last_is_num = true;
      }
      break;
      default:
        StackPush(str_len_sta,1);
        StackPush(data_sta,str[i]);
        last_is_num = false;
      break;
    }
  }
  //获取输出长度
  int res_len = StackPop(str_len_sta);
  //获取输出字符串
  char res_str[res_len+1];
  for (int i = res_len-1;i>=0;i--)
  {
    res_str[i] = StackPop(data_sta);
  }
  res_str[res_len] = '\0';
  puts (res_str);

  StackFree(str_len_sta);
  StackFree(data_sta);
  StackFree(opt_sta);
  return 0;
}