Chinaunix首页 | 论坛 | 博客

苦海澜石

首页　| 　博文目录　| 　关于我

khls27

  • 博客访问： 743345
  • 博文数量： 141
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1115
  • 用 户 组： 普通用户
  • 注册时间： 2014-03-17 14:32
个人简介

小公司研发总监，既当司令也当兵！

文章分类

全部博文（141）

推荐博文
相关博文
【RQNOJ】PID18 / 等价表达式

分类： LINUX

2017-07-22 14:26:29

题目描述

　　明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

　　这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？

　　这个选择题中的每个表达式都满足下面的性质：

　　1． 表达式只可能包含一个变量‘a’。

　　2． 表达式中出现的数都是正整数，而且都小于10000。

　　3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）

　　4． 幂指数只可能是1到10之间的正整数（包括1和10）。

　　5． 表达式内部，头部或者尾部都可能有一些多余的空格。


　　下面是一些合理的表达式的例子：

((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……

分析：表达式运算，一般都是用一个操作数栈，一个操作符栈，依据操作符的优先级逐级运算
本题的麻烦在于有一个变量，字符串操作起来就比较繁琐。
于是乎，就将多项式的每一项抽象为一个数据结构，因为每个项都可以由一个系数和指数唯一确定；那么一个多项式就可以表示为一组【系数+指数】的集合；


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  5. #define MAX_EXPONENT 100
  6. #define MAX_POLYNOMIAL 100

  8. typedef struct POLYNOMIAL_NODE {
  9.     unsigned int number;
  10.     short *coeff;
  11.     unsigned short *exp;
  12. } polynomial_t;


  15. polynomial_t* generate_from_list(short *exp_coeff, int len)
  16. {
  17.     polynomial_t *ret = NULL;
  18.     short *coeffs;
  19.     unsigned short *exps;

  21.     int cnt = 0;
  22.     int i, j;

  24.     for (i = 0; i < len; i++)
  25.     {
  26.         if (exp_coeff[i] != 0)
  27.         {
  28.             cnt++;
  29.         }
  30.     }
  31.     if (cnt == 0)
  32.     {
  33.         cnt = 1;// return 0
  34.     }

  36.     ret = (polynomial_t *)calloc(sizeof(polynomial_t), 1);
  37.     if (NULL == ret)
  38.     {
  39.         return NULL;
  40.     }

  42.     coeffs = (short *)calloc(sizeof(short), cnt);
  43.     exps = (unsigned short *)calloc(sizeof(unsigned short), cnt);
  44.     if (NULL == coeffs || NULL == exps)
  45.     {
  46.         return NULL;
  47.     }

  49.     j = 0;
  50.     for (i = 0; i < len; i++)
  51.     {
  52.         if (exp_coeff[i] != 0)
  53.         {
  54.             coeffs[j] = exp_coeff[i];
  55.             exps[j++] = i;
  56.         }
  57.     }
  58.     ret->number = cnt;
  59.     ret->coeff = coeffs;
  60.     ret->exp = exps;

  62.     return ret;
  63. }

  65. polynomial_t* polynomial_multip(polynomial_t *p1, polynomial_t *p2)
  66. {
  67.     short exp_coeff[MAX_EXPONENT] = { 0 };
  68.     int i, j;

  70.     for (i = 0; i < p2->number; i++)
  71.     {
  72.         for (j = 0; j < p1->number; j++)
  73.         {
  74.             exp_coeff[p1->exp[j] + p2->exp[i]] += p1->coeff[j] * p2->coeff[i];
  75.         }
  76.     }
  77.     return generate_from_list(exp_coeff, MAX_EXPONENT);
  78. }


  81. polynomial_t* polynomial_add(polynomial_t *p1, polynomial_t *p2)
  82. {
  83.     short exp_coeff[MAX_EXPONENT] = { 0 };
  84.     int i, j;

  86.     for (i = 0; i < p1->number; i++)
  87.     {
  88.         exp_coeff[p1->exp[i]] += p1->coeff[i];
  89.     }
  90.     for (i = 0; i < p2->number; i++)
  91.     {
  92.         exp_coeff[p2->exp[i]] += p2->coeff[i];
  93.     }
  94.     return generate_from_list(exp_coeff, MAX_EXPONENT);
  95. }

  97. polynomial_t* polynomial_sub(polynomial_t *p1, polynomial_t *p2)
  98. {
  99.     short exp_coeff[MAX_EXPONENT] = { 0 };
  100.     int i, j;

  102.     for (i = 0; i < p1->number; i++)
  103.     {
  104.         exp_coeff[p1->exp[i]] += p1->coeff[i];
  105.     }
  106.     for (i = 0; i < p2->number; i++)
  107.     {
  108.         exp_coeff[p2->exp[i]] -= p2->coeff[i];
  109.     }
  110.     return generate_from_list(exp_coeff, MAX_EXPONENT);
  111. }

  113. void polynomial_free(polynomial_t *p)
  114. {
  115.     if (!p)
  116.     {
  117.         return;
  118.     }
  119.     if (p->exp)
  120.     {
  121.         free(p->exp);
  122.     }
  123.     if (p->coeff)
  124.     {
  125.         free(p->coeff);
  126.     }
  127.     free(p);
  128. }

  130. void polynomial_print(polynomial_t *p)
  131. {
  132.     int i;
  133.     char sym;
  134.     char py[16];
  135.     if (!p)
  136.     {
  137.         return;
  138.     }

  140.     printf("polynomial<%p>, total %d:\n", p, p->number);
  141.     for (i = 0; i < p->number; i++)
  142.     {
  143.         memset(py, 0, 16);
  144.         if (p->coeff[i] < 0)
  145.         {
  146.             if (p->exp[i] == 0)
  147.             {
  148.                 sprintf(py, "%d", p->coeff[i]);
  149.             }
  150.             else if (p->exp[i] == 1)
  151.             {
  152.                 if (p->coeff[i] == -1)
  153.                 {
  154.                     sprintf(py, "-x");
  155.                 }
  156.                 else
  157.                     sprintf(py, "%dx", p->coeff[i]);
  158.             }
  159.             else
  160.             { if (p->coeff[i] == -1)
  161.                 {
  162.                     sprintf(py, "-x^%d", p->exp[i]);
  163.                 }
  164.                 else
  165.                     sprintf(py, "%dx^%u", p->coeff[i], p->exp[i]);
  166.             }
  167.         }
  168.         else
  169.         {
  170.             char* tmp = py;
  171.             if (i > 0)
  172.             {
  173.                 tmp[0] = '+';
  174.                 tmp++;
  175.             }

  177.             if (p->exp[i] == 0)
  178.             {
  179.                 sprintf(tmp, "%d", p->coeff[i]);
  180.             }
  181.             else if (p->exp[i] == 1)
  182.             {
  183.                 if (p->coeff[i] == 1)
  184.                 {
  185.                     sprintf(tmp, "x");
  186.                 }
  187.                 else
  188.                     sprintf(tmp, "%dx", p->coeff[i]);
  189.             }
  190.             else
  191.             {
  192.                 if (p->coeff[i] == 1)
  193.                 {
  194.                     sprintf(tmp, "x^%d", p->exp[i]);
  195.                 }
  196.                 else
  197.                     sprintf(tmp, "%dx^%d", p->coeff[i], p->exp[i]);
  198.             }
  199.         }
  200.         printf("%s", py);
  201.     }
  202.     printf("\n");
  203. }

  205. polynomial_t* polynomial_power(polynomial_t *p1, polynomial_t *p2)
  206. {
  207.     short exp_coeff[MAX_EXPONENT] = { 0 };
  208.     int i, j;
  209.     int exp = 0;
  210.     polynomial_t *ret;
  211.     polynomial_t *tmp;

  213.     if (p2->number != 1)
  214.     {
  215.         printf("polynomial power only support number\n");
  216.         return NULL;
  217.     }
  218.     exp = p2->coeff[0];

  220.     if (exp == 0)
  221.     {
  222.         exp_coeff[0] = 1;
  223.         return generate_from_list(exp_coeff, MAX_EXPONENT);
  224.     }
  225.     else if (exp < 0)
  226.     {
  227.         printf("polynomial power only support positive exponal\n");
  228.         return NULL;
  229.     }
  230.     if (exp == 1)
  231.     {
  232.         return p1;
  233.     }

  235.     ret = p1;
  236.     tmp = NULL;
  237.     while (exp > 1)
  238.     {
  239.         ret = polynomial_multip(ret, p1);
  240.         if (tmp)
  241.         {
  242.             polynomial_free(tmp);
  243.         }
  244.         tmp = ret;
  245.         exp--;
  246.     }
  247.     return ret;
  248. }

  250. char* parse_polynomial(char *str, polynomial_t **ptr)
  251. {
  252.     char *cur = str;
  253.     polynomial_t *ret = NULL;
  254.     short exp_coeff[2] = { 0 };
  255.     short coeff = 0;

  257.     if (*cur == 'x')
  258.     {
  259.         exp_coeff[1] = 1;
  260.         ret = generate_from_list(exp_coeff, 2);
  261.         *ptr = ret;
  262.         return ++cur;
  263.     }

  265.     while (*cur >= '0' && *cur <= '9')
  266.     {
  267.         coeff = coeff * 10 + (*cur - '0');
  268.         cur++;
  269.     }

  271.     exp_coeff[0] = coeff;
  272.     ret = generate_from_list(exp_coeff, 2);
  273.     *ptr = ret;
  274.     return cur;
  275. }

  277. polynomial_t* polynomial_comput(char *str)
  278. {
  279.     char symstack[MAX_POLYNOMIAL] = { 0, };
  280.     int symhead = -1;
  281.     polynomial_t *pstack[MAX_POLYNOMIAL] = { NULL };
  282.     int phead = -1;

  284.     polynomial_t *opt1;
  285.     polynomial_t *opt2;
  286.     polynomial_t *ret;
  287.     char optch;

  289.     char *cur;

  291.     if (!str)
  292.     {
  293.         return NULL;
  294.     }

  296.     cur = str;
  297.     while (*cur != '\0')
  298.     {
  299.         if (*cur == 'x' || (*cur >= '0' && *cur <= '9'))
  300.         {
  301.             cur = parse_polynomial(cur, &pstack[++phead]);
  302.             continue;
  303.         }
  304.         else
  305.         {
  306.             switch (*cur)
  307.             {
  308.             case '(': // 左括号直接入栈
  309.                 symstack[++symhead] = *cur;
  310.                 break;

  312.             case '^': // 查看符号栈顶是否为'^',如果是 弹出运算，其余的直接压栈
  313.                 if (symhead >= 0 && symstack[symhead] == '^')
  314.                 {
  315.                     optch = symstack[symhead--];
  316.                     opt2 = pstack[phead--];
  317.                     opt1 = pstack[phead--];

  319.                     ret = polynomial_power(opt1, opt2);
  320.                     pstack[++phead] = ret;
  321.                     symstack[++symhead] = *cur;
  322.                     polynomial_free(opt2);
  323.                     polynomial_free(opt1);
  324.                 }
  325.                 else
  326.                 {
  327.                     symstack[++symhead] = *cur;
  328.                 }
  329.                 break;

  331.             case '*': // 符号栈顶为'^' 或'*'则运算，否则压栈
  332.                 if (symhead >= 0 && (symstack[symhead] == '^' || symstack[symhead] == '*'))
  333.                 {
  334.                     optch = symstack[symhead--];
  335.                     opt2 = pstack[phead--];
  336.                     opt1 = pstack[phead--];

  338.                     if (optch == '^')
  339.                         ret = polynomial_power(opt1, opt2);
  340.                     else
  341.                         ret = polynomial_multip(opt1, opt2);

  343.                     pstack[++phead] = ret;
  344.                     symstack[++symhead] = *cur;
  345.                     polynomial_free(opt2);
  346.                     polynomial_free(opt1);

  348.                 }
  349.                 else
  350.                 {
  351.                     symstack[++symhead] = *cur;
  352.                 }
  353.                 break;
  354.             case '+':
  355.             case '-':
  356.                 if (symhead >= 0 & symstack[symhead] != '(')
  357.                 {
  358.                     optch = symstack[symhead--];
  359.                     opt2 = pstack[phead--];
  360.                     opt1 = pstack[phead--];

  362.                     if (optch == '^')
  363.                         ret = polynomial_power(opt1, opt2);
  364.                     else if (optch == '*')
  365.                     {
  366.                         ret = polynomial_multip(opt1, opt2);
  367.                     }
  368.                     else if (optch == '+')
  369.                     {
  370.                         ret = polynomial_add(opt1, opt2);
  371.                     }
  372.                     else if (optch == '-')
  373.                     {
  374.                         ret = polynomial_sub(opt1, opt2);
  375.                     }

  377.                     pstack[++phead] = ret;
  378.                     symstack[++symhead] = *cur;
  379.                     polynomial_free(opt2);
  380.                     polynomial_free(opt1);
  381.                 }
  382.                 else
  383.                     symstack[++symhead] = *cur;

  385.                 break;

  387.             case ')': // 如果是右括号，则一直运算直到找到左括号
  388.                 while (symhead >= 0 && symstack[symhead] != '(')
  389.                 {
  390.                     optch = symstack[symhead--];
  391.                     opt2 = pstack[phead--];
  392.                     opt1 = pstack[phead--];

  394.                     if (optch == '^')
  395.                         ret = polynomial_power(opt1, opt2);
  396.                     else if (optch == '*')
  397.                     {
  398.                         ret = polynomial_multip(opt1, opt2);
  399.                     }
  400.                     else if (optch == '+')
  401.                     {
  402.                         ret = polynomial_add(opt1, opt2);
  403.                     }
  404.                     else if (optch == '-')
  405.                     {
  406.                         ret = polynomial_sub(opt1, opt2);
  407.                     }

  409.                     pstack[++phead] = ret;
  410.                 }
  411.                 if (symstack[symhead] != '(')
  412.                 {
  413.                     printf("miss match of ')'\n");
  414.                     return NULL;
  415.                 }
  416.                 symhead--;
  417.                 break;
  418.             default:
  419.                 break;
  420.             }
  421.             cur++;
  422.         }
  423.     }

  425.     while (symhead >= 0)
  426.     {
  427.         optch = symstack[symhead--];
  428.         opt2 = pstack[phead--];
  429.         opt1 = pstack[phead--];

  431.         if (optch == '^')
  432.         {
  433.             ret = polynomial_power(opt1, opt2);

  435.         }
  436.         else if (optch == '*')
  437.         {
  438.             ret = polynomial_multip(opt1, opt2);
  439.         }
  440.         else if (optch == '+')
  441.         {
  442.             ret = polynomial_add(opt1, opt2);
  443.         }
  444.         else if (optch == '-')
  445.         {
  446.             ret = polynomial_sub(opt1, opt2);
  447.         }

  449.         pstack[++phead] = ret;
  450.         polynomial_free(opt2);
  451.         polynomial_free(opt1);
  452.     }

  454.     if (phead != 0)
  455.     {
  456.         printf("error : %d\n", phead);
  457.         polynomial_print(pstack[phead]);
  458.         return NULL;
  459.     }
  460.     return pstack[0];

  462. }

  464. int main(int argc, char **argv)
  465. {
  466.     polynomial_t *pyn;
  467.     char src[32] = "(x+1)^2^2-(x-x)^3+((x-1)*(x-1))";

  469.     pyn = polynomial_comput(src);
  470.     polynomial_print(pyn);
  471.     return 0;
  472. }

阅读(2788) | 评论(0) | 转发(0) |
0

上一篇：SSH 添加ssh公匙后还要求输入密码

下一篇：【网络攻击/测试工具】 hping3

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6