编程任务：编写一个程序，实现基本四则运算。

编程要点：

①  算符优先法；

②  栈结构和矩阵结构。

算法思路

算式由操作数、运算符和界限符组成，操作数为需要执行运算的数，运算符为加、减、乘、除，界限符为小括号。

算符优先法是根据算式相继出现的算符优先级来确定运算顺序，要比较算符的优先级，就要确定各种算符的优先级别，可以将算符间的优先级通过矩阵表示，在解析算式过程中通过查询算符优先级矩阵获取算符间的优先关系。

算式的运算符和界限符统称为算符，它们组成一个集合op{ +，-，*，/，(，) }。集合中任意两个算符a或b的优先级至多是下面三种关系之一。

a < b    a的优先级小于b的优先级

a = b    a的优先级等于b的优先级

a > b    a的优先级大于b的优先级

在算符优先算法中，可以采用下面的矩阵定义op集合算符间的优先关系，其中a为栈顶运算符，b为当前识别的运算符。

算符间的优先矩阵可以用字符类型的二维数组表示。

Java语言

/**
 * 算符集合用字符类型的数组表示
 */
char[] operator = {'+','-','*','/','(',')'};
/**
 * 算符优先级矩阵用字符类型的二维数组表示
 */
char[][]  matrix  = {{'>','>','>','>','<','>'},
{'>','>','>','>','<','>'},
{'<','<','<','<','<','>'},
{'<','<','<','<','<','>'},
{'<','<','<','<','<','='},
{'>','>','>','>','=','='}
};

解析算式时可以使用操作数和运算符两个栈，操作数栈用于存储操作数和运算结果，运算符栈用于存储算符。

算法的基本思想是：依次读入表达式每个字符，如是操作数进操作数栈，如是运算符，需要和运算符栈的栈顶运算符比较优先级，优先级若低于栈顶运算符，首先需要处理栈顶运算符并执行相关运算后再入栈，直至整个算式求值完毕。

下面用Java语言给出算法程序代码，程序假定输入的算式语法正确，没有对算式语法进行检测。

package com.milihua.algorithm.lineartable;
import java.util.Stack;
public class Evaluation {
/**
 * 算符集合用字符类型的数组表示
 */
char[] operator = {'+','-','*','/','(',')'};
/**
 * 算符优先级矩阵用字符类型的二维数组表示
 */
char[][]  matrix  = {{'>','>','>','>','<','>'},
{'>','>','>','>','<','>'},
{'<','<','<','<','<','>'},
{'<','<','<','<','<','>'},
{'<','<','<','<','<','='},
{'>','>','>','>','=','='}
};
/*
 * 表达式求值
 */
public  float evaluate(String expression) {
char[] tokens = expression.toCharArray();
Stack<Float> stackOfNum = new Stack<Float>();
Stack<Character> stackOfOps = new Stack<Character>();
for (int i = 0; i < tokens.length; i++) {
if (tokens[i] == ' ')
continue;
if (tokens[i] >= '0' && tokens[i] <= '9') {
StringBuffer sbuf = new StringBuffer();
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9') {
sbuf.append(tokens[i++]);
}
i--; // 回退一位
stackOfNum.push(Float.parseFloat(sbuf.toString()));
}
if( isOperator(tokens[i]) )
{
if( stackOfOps.empty() )
{
stackOfOps.push(tokens[i]);
}
else
{
char ch = hasPrecedence(tokens[i], stackOfOps.peek());
if( ch == '<' )
{
stackOfOps.push(tokens[i]);
}
else if( ch == '>' )
{
if( tokens[i] == ')' )
{
while(true)
{
if( stackOfOps.empty() )
break;
char op = hasPrecedence(tokens[i], stackOfOps.peek());
if( op == '=' )
{
stackOfOps.pop();
break;
}
else
{
stackOfNum.push(caculate(stackOfOps.pop(), stackOfNum.pop(), stackOfNum.pop()));
}
}
}
else
{
stackOfNum.push(caculate(stackOfOps.pop(), stackOfNum.pop(), stackOfNum.pop()));
stackOfOps.push(tokens[i]);
}
}
}
}
}
while (!stackOfOps.empty())
{
stackOfNum.push(caculate(stackOfOps.pop(), stackOfNum.pop(), stackOfNum.pop()));
}
return stackOfNum.pop();
 
}
/**
 * 判断读入的字符是否是运算符
 */
public boolean isOperator(char op)
{
for(int i = 0; i < operator.length; i++ )
{
if( op == operator[i] )
return true;
}
return false;
}
/**
 * 获取运算符在数组中的索引
 */
public int getOperator(char op)
{
for(int i = 0; i < operator.length; i++ )
{
if( op == operator[i] )
return i;
}
return -1;
}
/**
 * 判断op1和op2的优先级
 *
 */
public  char  hasPrecedence(char op1, char op2) {
int suffixop1 = getOperator(op1);
int suffixop2 = getOperator(op2);
if( suffixop1 == -1 || suffixop2 == -1 )
return 0;
return matrix[suffixop1][suffixop2];
}
 
/**
 * 执行运算
 *
 */
public  float caculate(char op, float b, float a) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0) {
throw new UnsupportedOperationException("Cannot divide by zero");
}
return a / b;
}
return 0;
 
}
 
/**
 * 输出栈
 *
 */
public void display(Stack  s)
{
for( int i = 0; i < s.size(); i++ )
{
System.out.print(s.get(i) + " ");
}
System.out.println();
}
}

evaluate函数是算法的核心，基本体现了前面给出的算法思想。其中对小括号做了特殊处理，当遇到算符')'时，需要对算符栈连续执行出栈操作，并执行相关运算，直至与栈顶运算符优先级相等或者栈已空。

hasPrecedence函数用于判断两个算符的优先级关系，算符的优先级矩阵由matrix给出，函数返回矩阵给出的优先级关系。

测试程序代码

package unittest;
import com.milihua.algorithm.lineartable.Evaluation;
import com.milihua.algorithm.lineartable.Expression;
public class EvluationTest {
 
public static void main(String[] args) {
// TODO Auto-generated method stub
Evaluation  evaluation = new Evaluation();
System.out.println(evaluation.evaluate("2*(3+5)"));
System.out.println(evaluation.evaluate("100 * 2 + 12"));
System.out.println(evaluation.evaluate("100 * ( 2 + 12 )"));
System.out.println(evaluation.evaluate("100 * ( 2 + 12 ) / 14"));
System.out.println(Expression.evaluate("5 * ( 6 + 12 ) * 5 - 12"));
System.out.println(Expression.evaluate("3+12*18-60*15+3*(3+2)"));
}
 
}

栈结构

栈结构是一种特殊的线性表，限定仅在表的一端进行元素的插入和删除。当表中没有元素时，称为空栈。若给定栈：

S = (a1，a2，……，an)

则称a1是栈底元素，an是栈顶元素，表中元素按a1，a2，……，an的次序进栈，出栈的顺序是an，……，a2，a1。也就是说，栈结构的元素访问原则是后进先出，也称为后进先出的线性表的，如下图所示。

栈结构运算有入栈、出栈、访问栈顶元素、栈置空四种基本运算。

（1）入栈运算

该运算在长度为n的栈中，将元素置入栈顶。若栈已满，返回出错信息。

（2）出栈运算

该运算在长度为n的栈中，取出栈顶元素，并从栈中删除该元素。若栈为空，返回出错信息。

（3）访问栈顶元素运算

该运算在长度为n的栈中，取出栈顶元素。若栈为空，返回出错信息。

（4）栈置空运算

该运算将栈置为空栈。