编程与数学：算符优先法与算式解析

编程实践楼 2021-10-05

667

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

编程要点：

① 算符优先法；

② 栈结构和矩阵结构。

算法思路

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

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

算式的运算符和界限符统称为算符，它们组成一个集合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)"));
  }


}

数据库

文章转载自编程实践楼，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

编程与数学：算符优先法与算式解析

评论