Expression

判断一个基本的四则运算的算术表达式是否合法，如果合法求出该算术表达式的值。

实例说明: 例子中变量为字母与数字的组合且不能以数字开头,变量中可有英文输入法下的点"."和下划线"_",合法的变量如:qqq、aaa_uuu、yyy6、yyy_a.b等。程序中若需要计算表达式的值，则只需要将该变量的值替换为对应的数值即可。下面例子中的词法分析器的结果形式为 (word,code) 的形式，word为单词部分，code为单词编码。程序涉及的单词及编码会在后面进行说明。

eg-1:

表达式：3 * 5 / (12 + 11)
词法分析所得的结果：[(3,5), (*,3), (5,5), (/,4), ((,6), (12,5), (+,1), (11,5), (),7)]
表达式是否正确：true
计算表达式的值：0.6522

eg-2:

表达式：((12*(2.50-1.05)-10)+90)
词法分析所得的结果：[(3,5), (*,3), (5,5), (/,4), ((,6), (12,5), (+,1), (11,5), (),7)]
表达式是否正确：true
计算表达式的值：97.40

eg-3:

表达式：a_qq.b+b+c+f+2+d7+t9
词法分析器所得的结果：[(a_qq.b,5), (+,1), (b,5), (+,1), (c,5), (+,1), (f,5), (+,1), (2,5), (+,1), (d7,5), (+,1), (t9,5)]
表达式是否正确：true
计算表达式的值：此处表达式为变量，只能做表达式是否正确的判断，若要计算表达式的值，则需要将表达式中的变量的值替换为对应的数值即可。

eg-4:

表达式：a_qq.b+b+c+f)
词法分析所得的结果：[(a_qq.b,5), (+,1), (b,5), (+,1), (c,5), (+,1), (f,5), (),7)]
表达式是否正确：false

eg-5:

表达式：a_qq.b+5b+6cu+f
词法分析所得的结果：[(a_qq.b,5), (+,1), (5,5), (b,5), (+,1), (6,5), (cu,5), (+,1), (f,5)]
表达式是否正确：false(变量以数字开头)

程序整体思路如下：

1. 对输入的表达式字符串进行去除空格，然后对表达式进行词法分析获取该表达式的词库。
2. 对所得的词库使用算数表达式文法G进行语法分析。
3. 若语法分析正确，则将1中所得的算术表达式由中缀表达式转换为后缀表达式。
4. 使用数据结构中的栈对后缀表达式进行求值，进而求出该算术表达式的值。

1.词法分析

在对输入的算术表达式进行词法分析前，我们对程序中所涉及的单词及单词种别编码进行如下规定：

单词符号	种别编码
+	1
-	2
*	3
/	4
数字/变量	5
(	6
)	7

为了存储分析出的单词信息，我们这里定义了一个Word类来专门存储,其代码如下：

Word.java

class Word{
	
	String word;  //单词部分
	
	Integer code;  //单词种别编码

	@Override
	public String toString() {
		return "("+word+","+String.valueOf(code)+")";
	}
	
	public Word(String word,Integer code) {
		this.word=word;
		this.code=code;
	}
}

词法分析即对输入的算术表达式进行逐个字符扫描,依次识别出表达式中的单词，其识别算法封装在程序中的wordAnalysis方法中，其识别算法如下：

先对输入的算术表达式去除空格符号处理。参见程序中的String expStrNoSpace=remove(experssionStr, ' ')代码。
循环遍历1处理后的算术表达式:

如果当前字符是操作符(+ - * /)或者是左括号'('与右括号')',直接将该字符加入到我们用于存储单词的集合List中，字符游标前移。

如果当前字符是字母或者是英文符号下的下划线'',则字符右边继续前移，如果前移的字符游标是'.',则字符游标继续前移，若前移的游标指向的字符为字母、数字或''，则字符游标继续前移，直到遇到游标所指的字符为操作符时游标停止前移，此时现将识别出的变量单词存入到单词集合List中,游标前移一位，将识别出的操作符存入List中，游标前移继续扫描识别。

如果当前字符是数字，游标继续前移,直到游标所值得字符为非数字时，将游标当前识别出的数字字符存入到List中,游标继续前移扫描识别单词。

重复上述操作，直至扫描完整个算术表达式字符串。

2. 语法分析

对识别出的单词使用算术表达式文法G进行语法分析,若该算术表达式的语法分析结果正确，则以已识别出的单词作为输入,将该算术表达式的中缀表达式的转换为后缀表达式。

对3输出的后缀表达式使用操作符栈和操作数栈两个栈配合计算出该算术表达式的值。

zq0757/Expression