数据结构与算法(三)

本文主要是介绍数据结构与算法(三)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在上一篇文章中，我们完整实现了计算器功能，但是还存在一些问题：
解决不支持多位数

不支持多位数的原因就在于：在扫描表达式时，没有考虑多位数的解析。那么思路是：当我们当前的数据是数字的时候，不能直接添加，而是保存到一个String中，需要判断下一位数据是不是字符或者没有下一位，如果是，将字符串转换成int类型数据添加到数栈中，如果不是直接扫描下一位数据继续判断，直到遇到符号或者结尾才结束，将数添加到数栈。当一个数添加到数栈以后，字符串需要重置，否则会出现错误。

在扫描表达式这一步进行修改支持多位数

//当我们遍历的数据是数字的时候
numCh += ch;//numCh为String类型，我们在遍历循环之前定义

//判断当前遍历的下一位还是不是数字，如果当前遍历元素是最后一位直接结束
if(index == express.length() -1){
    numStack.push(Integer.parseInt(numCh));
}else{
    //当下一个元素是符号的时候才会添加，numCh进行重载，否则数字保存在numCh中
    if(numStack.isOper(express.substring(index+1,index+2).charAt(0))){
        numStack.push(Integer.parseInt(numCh));
        numCh = "";
    }
}

三种表达式

前缀表达式(波兰表达式)

前缀表达式又称为 波兰表达式，前缀表达式的 运算符位于操作数之前。

例如：(3+4)x5-6 对应的前缀表达式为：- x + 3 4 5 6

注意：前面这个表达式是一个中缀表达式，对应的是后面的这个前缀表达式。它的符号出现的顺序与中缀的顺序不一致。

前缀表达式中的符号顺序，就是他求值的规定了

前缀表达式求值过程

1. 从 右到左 扫描表达式

2. 遇到 数字 时，将数字压入堆栈

3. 遇到 运算符 时

   弹出栈顶的两个数（栈顶和次顶），用运算符对它们做相应的计算，并将结果入栈。

   计算顺序是：先 弹出来的 (运算符) 后 弹出来的

然后重复以上步骤，直到表达式的最左端，最后运算出的值则是表达式的值。

看完前缀表达式的计算逻辑，那么你要明白的是，从一个 中缀表达式 转换为 前缀表达式 时，优先级顺序是已经处理好的，因为在求值时，不进行优先级的判定

例如：(3+4)x5-6 对应的前缀表达式为：- x + 3 4 5 6，前缀表达式求值步骤如下：

1. 从右到左扫描，将 6、5、4、3 压入栈

2. 遇到 + 运算符时：

   将弹出 3 和 4（3 为栈顶元素，4 为次顶元素），计算出 3 + 4 = 7，将结果压入栈

3. 遇到 x 运算符时

   将弹出 7 和 5，计算出 7 x 5 = 35，将 35 压入栈

4. 遇到 - 运算符时

   将弹出 35 和 6，计算出 35 - 6 = 29，压入栈

5. 扫描结束，栈中留下的唯一一个数字 29 则是表达式的值

中缀表达式

中缀表达式就是 常见的运算表达式，如 (3+4)x5-6。

中缀表达式的求值是人类最熟悉的，但是对于计算机来说却不好操作：

• 需要计算运算符的优先级
• 对于中括号来说，笔者想不出实现办法

因此，在计算结果时，往往会将 中缀表达式 转成其他表达式，一般转成后缀表达式。

后缀表达式(逆波兰表达式)

后缀表达式 又称为 逆波兰表达式，与前缀表达式类似，只是 运算符 位于 操作数之后。

比如：(3+4)x5-6 对应的后缀表达式 3 4 + 5 x 6 -

再比如：

后缀表达式求值过程

1. 从 左到右 扫描表达式

2. 遇到 数字 时，将数字压入堆栈

3. 遇到 运算符 时

   弹出栈顶的两个数（栈顶和次顶），用运算符对它们做相应的计算，并将结果入栈。

   计算顺序是：后 弹出来的 (运算符) 先 弹出来的

然后重复以上步骤，直到表达式的最右端，最后运算出的值则是表达式的值。

比如：(3+4)x5-6 对应的后缀表达式 3 4 + 5 x 6 -

1. 从左到右扫描，将 3、4 压入堆栈

2. 扫描到 + 运算符时

   将弹出 4 和 3，计算 3 + 4 = 7，将 7 压入栈

3. 将 5 入栈

4. 扫描到 x 运算符时

   将弹出 5 和 7 ，计算 7 x 5 = 35，将 35 入栈

5. 将 6 入栈

6. 扫描到 - 运算符时

   将弹出 6 和 35，计算 35 - 6 = 29，将 29 压入栈

7. 扫描表达式结束，29 是表达式的值

逆波兰计算器

完成一个逆波兰计算器，需求如下：

1. 输入一个 逆波兰表达式，使用栈 Stack（JDK 自带），计算器结果

2. 支持 小括号 和 多位数

   主要这里是讲解数据结构，因此简化为只对整数计算

注意咯：知道逆波兰表达式是什么后，相对来说，实现还是比较容易的，难点其实是在于中缀表达式如何转换为后缀表达式，因为这涉及到运算符的优先级问题。在前面我们实现的时候，其实就是这个运算符优先级问题很刺手。而前缀、后缀表达式里面表达式的优先级在形成表达式时就已经确定了。

public class PolandNotation {
    public static void main(String[] args) {
        //使用逆波兰表达式计算结果
        String suffixExpress = "4 5 * 8 - 60 + 8 2 / +";
        List<String> res = getString(suffixExpress);
        System.out.println("res = " + res);

        int result = 0;
        try {
            result = calculation(res);
        } catch (Exception e) {
            System.out.println(e.getMessage());;
        }
        System.out.println("计算结果为：" + result);

    }
    //将逆波兰表达式转分割，装入ArrayList集合，方便后面进行运算
    public static List<String> getString(String suffix){
        String[] splits = suffix.split(" ");
        List<String> res = new ArrayList<>();
        for(String s: splits){
            res.add(s);
        }
        return res;
    }
    //计算结果
    public static int calculation(List<String> list){
        int result = 0;
        Stack<String> stack = new Stack<>();
        for(String s : list){
            //判断是不是一个数字
            if(s.matches("\\d+")){
                //使用正则表达式判断
                stack.push(s);//入栈
            }else{
                //进行运算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                if(s.equals("+")){
                    result = num1 + num2;
                }else if(s.equals("-")){
                    result = num1 - num2;
                }else if(s.equals("*")){
                    result = num1 * num2;
                }else if(s.equals("/")){
                    result = num1 / num2;
                }else{
                    throw new RuntimeException("运算符错误");
                }
                //将结果入栈
                stack.push(result + "");
            }
        }
        //最后在栈中的就是计算结果
        return Integer.parseInt(stack.pop());
    }
}

中缀表达式转后缀表达式

通过前面的逆波兰计算器的代码实现，可以看到：后缀表达式对于计算机来说很方便，但是对于人类来说，后缀表达式却不是那么容器写出来的。

中缀表达式转后缀表达式步骤：

1. 初始化两个栈：

   • 运算符栈：s1
   • 中间结果栈：s2

2. 从左到右扫描中缀表达式

3. 遇到操作数时，将其压入 s2

4. 遇到运算符时

   比较 它 与 s1 栈顶运算符的优先级：

   1. 如果 s1 为空，或则栈顶运算符号为 ( ，则将其压入符号栈 s1
   2. 如果：优先级比栈顶运算符 高，也将其压入符号栈 s1
   3. 如果：优先级比栈顶运算符 低 或 相等，将 s1 栈顶的运算符 弹出，并压入到 s2 中

   再重复第 4.1 步骤，与新的栈顶运算符比较（因为 4.3 将 s1 栈顶运算符弹出了）

   这里重复的步骤在实现的时候有点难以理解，下面进行解说：

   1. 如果 s1 栈顶符号 优先级比 当前符号 高或则等于，那么就将其 弹出，压入 s2 中（循环做，是只要 s1 不为空）

      如果栈顶符号为 (，优先级是 -1，就不会弹出，就跳出循环了

   2. 跳出循环后，则将当前符号压入 s1

5. 遇到括号时：

   1. 如果是左括号 ( ：则直接压入 s1

   2. 如果是右括号 )：

      则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 为止，此时将这一对括号 丢弃

6. 重复步骤 2 到 5，直到表达式最右端

7. 将 s1 中的运算符依次弹出并压入 s2

8. 依次弹出 s2 中的元素并输出，结果的 逆序 即为：中缀表达式转后缀表达式

下面进行举例说明：

将中缀表达式：1+((2+3)*4)-5 转换为后缀表达式

由于 s2 是一个栈，弹出是从栈顶弹出，因此逆序后结果就是 1 2 3 + 4 * + 5 -

在学习和使用上有两个层次：

1. 应用层次：别人发明出来的东西，你学习、理解它，并灵活运用它
2. 自创：你自己发明一个东西出来，并使用它

那么这里的中缀转后缀表达式的思路步骤，则属于第一个层次，相关的计算机专家之类的，发明出来了。我们要理解它并灵活运用它。等你能力达到一定层度时，有可能发明出来一个算法。

再比如：绝世武功 -> 降龙十八掌，别人已经创造出来了，你不去学习理解它，如何加以改进并自创？如果没有人教你，你怎么能学会降龙十八掌？

逆波兰表达式计算器代码实现

public class PolandNotation {
    public static void main(String[] args) {
        String str = "1+((2+3)*4)-5";
        List<String> list = toInfixExpressionList(str);
        System.out.println("list = " + list);

        List<String> result = parseSuffixExpressionList(list);
        System.out.println("result:" + result);
        //计算结果
        System.out.println(calculation(result));


    }
    //中缀表达式转后缀表达式
    public static List<String> parseSuffixExpressionList(List<String> list){
        //1.初始化一个栈用来保存符号，直接使用ArrayList来保存中间数据，保存的结果输出就是后缀表达式
        Stack<String> operStack = new Stack<>();
        List<String> result = new ArrayList<String>();
        //2.从左到右遍历中中缀表达式
        for(String c : list){
            if(c.matches("\\d+")){
                //当前表达式是一个数，直接添加到中间数据中
                result.add(c);
            }else{
                //当为符号的情况
                if(operStack.isEmpty()){
                    //当符号栈为空的时候，或者遇到“("就直接添加
                    operStack.push(c);
                }else if(c.equals("(")){
                    operStack.push(c);
                }else if(c.equals(")")){
                    //当当前符号为)的时候，弹出栈中数据到中间结果中，直到遇到(就结束
                    while(!operStack.peek().equals("(")){
                        result.add(operStack.pop());
                    }
                    //将符号"("弹出
                    operStack.pop();
                }else{
                    //进行优先级的比较
                    while(operStack.size() != 0 && Operational.priority(c) <= Operational.priority(operStack.peek())){
                        //当我们要添加的符号的优先级小于或者等于栈顶元素的时候,就将栈顶元素取出加入到中间结果
                        result.add(operStack.pop());
                    }
                    operStack.push(c);//将当前符号加入栈中
                }
            }
        }
        //将符号栈中的符号添加至中间结果
        while(!operStack.isEmpty()){
            result.add(operStack.pop());
        }
        return result;
    }
    //将一个中缀表达式分割并存放到一个ArrayList集合中，方便我们后面转换操作
    public static List<String> toInfixExpressionList(String str){
        List<String> list = new ArrayList<>();
        String s = null;
        int index = 0;//遍历str字符串的索引
        char c;//保存每次遍历的数据
        do{
            c = str.charAt(index);
            s = "";//重置字符串
            //判断这个数据是字符还是数据
            if(c >= 48 && c <= 57){
                //是数字
                s += c;
                //查看下一个是否是数字,注意要防止最后一个元素是多位数，出现索引越界的情况，
                // 所以这里只能判断到length-2就进入循环
                while(index < (str.length()-1) && (str.charAt(index+1) >= 48)
                        && (str.charAt(index+1) <= 57) ){
                    //后一个还是数字
                    index++;
                    s += str.charAt(index);
                }
                list.add(s);
                index++;

            }else{
                //是字符，直接加入
                s += c;
                list.add(s);
                index++;
            }


        }while(index < str.length());
        return list;
    }
    //将逆波兰表达式转分割，装入ArrayList集合，方便后面进行运算
    public static List<String> getString(String suffix){
        String[] splits = suffix.split(" ");
        List<String> res = new ArrayList<>();
        for(String s: splits){
            res.add(s);
        }
        return res;
    }
    //计算结果
    public static int calculation(List<String> list){
        int result = 0;
        Stack<String> stack = new Stack<>();
        for(String s : list){
            //判断是不是一个数字
            if(s.matches("\\d+")){
                //使用正则表达式判断
                stack.push(s);//入栈
            }else{
                //进行运算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                if(s.equals("+")){
                    result = num1 + num2;
                }else if(s.equals("-")){
                    result = num1 - num2;
                }else if(s.equals("*")){
                    result = num1 * num2;
                }else if(s.equals("/")){
                    result = num1 / num2;
                }else{
                    throw new RuntimeException("运算符错误");
                }
                //将结果入栈
                stack.push(result + "");
            }
        }
        //最后在栈中的就是计算结果
        return Integer.parseInt(stack.pop());
    }
}
//定义一个工具类，主要用于比较运算符的优先级
class Operational{
    //定义一个操作符类，用于比较
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 2;
    private static final int DIV = 2;
    private static final int OPER = 0;

    public static int priority(String c){
        int res = -1;
        switch(c){
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            case "(":
                res = OPER;
                break;
            default:
                System.out.println("操作符非法");
                break;
        }
        return res;
    }
}

这篇关于数据结构与算法(三)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！