咿咿...求制作《数学题系统》显示带数学符号的题目的思路

正太君

咿咿...最近聪聪有一个想法呢，那就是做一个《数学题系统》，里面预存各种各样的数学题（以某个module下的常数存储）

RUBY 代码复制

module Chuyi
  TIMU ={}
end
module Chuer
  TIMU ={}
end
module Chusan
  TIMU = {
    0 => ["已知函数f(x)=(√(1-(cosx)^2+x^2)/2，那么当x=1时的函数值是______", "(√2)/2"]
    1 => ["......","......"]
    2 => ["......","......"]
    ......
  }
end

module Chuyi


  TIMU ={}


end


module Chuer


  TIMU ={}


end


module Chusan


  TIMU = {


    0 => ["已知函数f(x)=(√(1-(cosx)^2+x^2)/2，那么当x=1时的函数值是______", "(√2)/2"]


    1 => ["......","......"]


    2 => ["......","......"]


    ......


  }


end

然后系统会随机抽题，答对就有奖励，用以激发学习兴趣...但是现在无法解决公式的显示问题咿咿，请大家帮忙想想办法...
这里引入三个名词：显示语言、输入语言、脚本语言
【输入语言】：输入到TIMU中使用的语言，不同的输入方式会影响到显示语言的显示，比如√a和a^(1/2)是有区别的，前一个显示根号，后一个显示1/2为指数...
【显示语言】：完全数学公式化后显示给玩家看的最终效果的语言...
【脚本语言】：系统读的语言，无需再次翻译就可以直接进行脚本运算...

语言	写法比较
输入语言	“已知函数f(x)=(√(1-(cosx)^2+x^2)/2，那么当x=1时的函数值是______"
显示语言
脚本语言	f =(Math.sqrt(1-(Math.cos(x))**2)+x**2)/2

现在难点就在于怎么把【输入语言】翻译成【显示语言】，求大神指点迷津...
显示根号和分数线估计是必须用到图形绘制、然后还要计算翻译之后公式的高度和宽度，调整显示语言的行间距，公式前后的文字间距...
把【输入语言】翻译成【脚本语言】相对容易，暂时不问这个...
把【显示语言】翻译成【脚本语言】是判断填空题答案正确性的一种方法，但是难上加难，所以暂时不奢求这个...

xiaorang

爱学习的孩子！{:2_284:}

RyanBern

提出一个比较自然的思路，但是需要一些先修知识。
在这里详细写一个算法思想（希望能求个糖啥的）
不过我相信聪仔能很快理解。
在这里要运用的概念：二叉树，树的周游次序，中根次序周游，后根次序周游，中缀表达式，后缀表达式，递归算法，栈（数据结构）。
聪聪可以自行wiki一下。
（一）问题的提法
首先先明确一下我们的任务，我们是要把一个自然表达式翻译成你所谓的“显示表达式”。聪聪其实在主楼里面提到，将所谓“输入语言”翻译成“脚本语言”（并求其值）是一件容易的事情，实际上却不是这样。在这里我们假设聪聪没有学习过数据结构等内容，那么由输入的自然语言得到其表达式的值，其实还是比较麻烦的（这里有点像我们平时用的casio高级计算器的原理，输入一个表达式直接求值）。当然不排除LZ已经提前学习过大学数据结构课程或者是学过信息竞赛。
扯得有点远了，其实我想说，要解决这个问题，就必须先从LZ提到的“输入语言”转换为“脚本语言”谈起。
（二）计算机识别“输入语言”指令——后缀表达式的应用
我们回到刚才那个问题，如何输入一串自然表达式（字符串或字符数组形式），让计算机求出表达式的值？
例如，我输入2 + 3 * 4，则计算机输出14，我输入(2 + 3) * 4，则计算机输出20。
这个问题看似简单，你可能会说在脚本编辑器输入这个命令不就得了？但是实际的输入形式是字符串或者字符数组（T君：那我eval一下不就得了？）。在这里，我们恰恰是实现了eval关于数学表达式的细节过程，因为这个过程会直接引导我们解决最终的问题。
好了，RB你废话真多，快说说怎么办。
首先，我们习惯的“自然表达式”形式，计算机是不习惯的，因为自然表达式最大缺点就是如果你从前往后看，那么你基本上是无法确定该怎么计算的。
例如，还是上面那个表达式，假如你看到了2 + 3，而后面的 * 4没有看到，你知道这个表达式还没完，那你敢利用你刚刚看到的表达式计算吗？显然不能。因为有些运算符优先度高，它们会轻易地改变运算顺序。计算机也是一样，如果光看自然表达式，计算机也无法确定该怎么计算。因此，这种表达式对计算机来说，是不好的，必须找一个更好的才行。
因此，后缀表达式应运而生。后缀表达式，简单来说就是把操作符放在操作数的后面，而不是两个操作符中间（二元运算符）。而我们的自然表达式是把操作符放在两个操作数中间的，因而自然语言也叫中缀表达式。
例如，2 + 3 * 4的后缀表达式为：2 3 4 * +
例如，(2 + 3) * 4的后缀表达式为：2 3 + 4 *
通过这么一变，我们看到后缀表达式把原来我们熟悉的自然表达式变成了不知道什么鬼的一串东西，我们很不喜欢它，但是计算机很喜欢它。因为这种表达式，计算机是很容易计算的。
例如，计算后缀表达式2 3 4 * +的时候，先读取三个数字，然后读取到了乘号*，这样，拿出乘号左边的两个数3和4，计算得12，然后把3 4 *这个部分换成12，现在表达式就变成了2 12 +，这样就再计算2 + 12，得到最终结果14。
例如，计算后缀表达式2 3 + 4 *的时候，先读取两个数字，然后读取加号+，这样，拿出加号左边的两个数2和3，计算得5，然后把2 3 +这个部分替换成5，现在表达式变成了5 4 *，计算5 * 4，得到最终结果是20。
实际上，任何一个算式，都会有唯一一个后缀表达式对应。
而且我们注意到，后缀表达式完全不需要括号，这点是自然表达式没有的结构。

所以，按照主楼的式子，如果把cos这样的一元函数看作一个一元运算符，那么相应的后缀表达式应该为：
f(x) = 1 x cos 2 ^ - x 2 ^ + √ 2 /
如果看明白前面的就验证一下。


上面这个图可以参考，这是表达式的二叉树写法，图中蓝色结点表示操作符，而绿色结点表示操作数。注意每一个结点的下方最多有两个结点与其相连，这两个结点有左右之分。
而图中，结点左上角红色数字代表中缀表达式的写法次序（实际是中根次序周游），右上角橙色数字代表后缀表达式的写法次序（实际是后根周游次序）。这部分内容作为拓展内容，建议在弄清“二叉树”“树的周游”之后再来阅读。

现在，我们引出第一个小问题，如何把中缀表达式转换成后缀表达式。

（三）生成后缀表达式——栈的应用
现在我们要制造后缀表达式了，当然原料是我们的中缀表达式。在这里我们要借助“栈”这个有力的数据结构。
作为一种常用数据结构，栈可以看作是有特殊结构的容器，具有“先入后出”的特点。即第一个进入该容器的元素，往往是最后一个出来。换句话说，如果从栈里面取出一个元素，那么取出的这个元素必定是所有元素中“最后进去的那一个”。打个比方，就好像餐馆的服务生洗盘子，盘子洗好了就堆成一摞。显然，一摞盘子，最下面的那个盘子肯定是最先洗好的，但是你拿盘子的时候，多数正常人会先拿最上面那一个，即“最后洗好的那个盘子”。从这个角度理解栈会轻松很多。如果想要了解更多，还是wiki一下为好。

现在我们引入后缀表达式的构造思路，为此，我们引入“优先级”的概念，我们知道，运算符有一定的优先级，这会影响到运算次序和结果。
在这里我们定义运算符优先级次序：
函数符号（例如cos，开方运算√也算作函数符号） > 乘方（^） > 乘除（* /） > 加减（+ - ）
因为中缀表达式中存在括号，在这里我们定义左括号的优先级比所有运算符优先级都低，定义右括号的优先级比所有运算符都高（也可不定义）。
因此，可以写出以下算法：
1.从左到右读入操作符和操作数。
2.如果读取到操作数，直接输出。
3.如果读取到操作符（这里不包括括号），则需要把操作符放入栈中。
放的时候要保证一个原则，就是将此操作符放入栈之前，要保证栈为空，或者栈顶操作符的优先级低于（不允许等于）当前操作符。否则，要逐一从栈顶弹出运算符并输出，直到上面的条件被满足为止。
4.如果读取到左括号，无视优先级，直接放入栈中。
5.如果读取到右括号，则立即逐一将栈顶操作符弹出并输出，直到遇到左括号为止（左括号也弹出但并不输出）。
6.读取完毕后，逐一弹出并输出栈内所剩的所有运算符。
下面是一个例子：

步骤	待处理中缀表达式 头——尾	栈状态 顶——底	输出的后缀表达式 （头——尾）
1	(2 + 3) * 4
2	2 + 3) * 4	(
3	+ 3) * 4	(	2
4	3) * 4	+(	2
5	) * 4	+(	2 3
6	* 4		2 3 +
7	4	*	2 3 +
8		*	2 3 + 4
9			2 3 + 4 *

具体代码请用Ruby写出。

（四）由后缀表达式生成显示表达式（LaTeX显示语言）
在这里采取一种递归思想，因为对于每个表达式，只有两部分组成：操作符，操作数（在这里我们假设操作数的个数小于等于2）。那么，我们只需要对每一个操作符写一个绘制bitmap的通用方法即可。
例如，对于操作符'+'，把左右两侧的表达式看作一个整体，那么我们只需要以下几步：
子表达式1 + 子表达式2
1.绘制子表达式1
2.绘制'+'
3.绘制子表达式2
例如，子表达式1绘制完毕后是一个32*16的矩形，子表达式2绘制完毕后是一个48*16的矩形，'+'符号是一个16 * 16的矩形，那么绘制结果就是一个96 * 16的矩形。
至于子表达式如何绘制，就是递归处理了。
为此，利用栈来实现递归处理方法，这里运用后缀表达式求值方法。
算法如下：
1.读取后缀表达式。
2.如果读取到操作数，就将其变为表示操作数的bitmap对象，并将bitmap对象放入栈中。
3.如果读取到操作符，那么按照操作符需要的操作数，从栈中弹出相应个数的bitmap对象，然后根据操作符绘制新的bitmap，并释放旧bitmap，把新bitmap放入栈中。
4.如此下去，处理完毕后，栈顶的bitmap对象就是需要绘制的bitmap对象。
简略伪代码如下：

RUBY 代码复制

module RB
end
module RB::LaTeX_Imitate
  # 生成显示表达式，expression为相应后缀表达式
  def self.generate(expression)
    stack = []
    # 表达式不空才进行循环  
    while element = expression.pop 
      if element 为操作数
        bmp = Bitmap.new(宽, 高)
        bmp.draw_text(x, y, w, h, element.to_s)
        stack << bmp
      elsif element 为操作符
        draw_expression(element, stack) # 定义在后面
      end
    end
    return stack[0]
  end
  # 依照element和stack绘制新表达式的bitmap
  def self.draw_expression(element, stack)
    case element
    when "+"
      bmp1 = stack.pop
      bmp2 = stack.pop
      bmp_new = Bitmap.new(宽, 高)
      将bmp1, bmp2, '+'合并到 bmp_new中
      stack << bmp_new
      # 记得释放
      bmp1.dispose
      bmp2.dispose
    when "-"
      # 请自己定义
    end
  end
end

module RB


end


module RB::LaTeX_Imitate


  # 生成显示表达式，expression为相应后缀表达式


  def self.generate(expression)


    stack = []


    # 表达式不空才进行循环  


    while element = expression.pop 


      if element 为操作数


        bmp = Bitmap.new(宽, 高)


        bmp.draw_text(x, y, w, h, element.to_s)


        stack << bmp


      elsif element 为操作符


        draw_expression(element, stack) # 定义在后面


      end


    end


    return stack[0]


  end


  # 依照element和stack绘制新表达式的bitmap


  def self.draw_expression(element, stack)


    case element


    when "+"


      bmp1 = stack.pop


      bmp2 = stack.pop


      bmp_new = Bitmap.new(宽, 高)


      将bmp1, bmp2, '+'合并到 bmp_new中


      stack << bmp_new


      # 记得释放


      bmp1.dispose


      bmp2.dispose


    when "-"


      # 请自己定义


    end


  end


end

（五）细节处理——括号的问题
由于后缀表达式是没有括号的，但是输出的最终结果往往都有括号，因此必须要小心括号的写法。
因此，可以在上述self.draw_expression方法里，加入一个括号绘制标志brackets，如果有此标志就绘制括号。
至于括号标志的判断，需要根据当前运算符，子表达式最外层的运算符联合确定。因此还需要加一个数据结构，在这里不再赘述。
值得注意的是，像分数线，根号这种特殊的符号，是不用加括号的。
这个细节就请LZ自行完成吧。

仓促中写了这么多，难免其中有考虑不周之处，不过希望能有所启发。

taroxd

LaTeX （大雾）