解析算术表达式并求值
试题类型:编程题    难度:中等

编写一个程序,具体要求为:

用户输入四则算式表达式,程序解析表达式并求值。


提示:

表达式都是由操作数、运算符和界限符组成的。在编程语言中操作数既可以是常数,也可以是变量或常量的标识符;运算符可以分为运算符、关系运算符和逻辑运算符等三类;基本界限符有小括号、中括号和表达式结束符等。

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

全部题解
解析算术表达式并求值
编程训练营官方题解

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

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

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

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

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

31.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)"));
}
 
}


  • 备案号:鲁ICP备15001146号
  • @1997-2018 潍坊米粒花网络技术有限公司版权所有