算符优先法与算式解析
5339字,阅读需时18分钟
来自专栏
课程/专栏

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

编程要点:

①  算符优先法;

②  栈结构和矩阵结构。

算法思路

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

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

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

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

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

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

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

07.PNG

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

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。也就是说,栈结构的元素访问原则是后进先出,也称为后进先出的线性表的,如下图所示。

08.png

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

(1)入栈运算

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

(2)出栈运算

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

(3)访问栈顶元素运算

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

(4)栈置空运算

该运算将栈置为空栈。

我要评论
全部评论