数据结构Stack之四则运算

简介: 数据结构Stack之四则运算

题目

描述

输入一个表达式(用字符串表示),求这个表达式的值。

保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’, ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。


数据范围:表达式计算结果和过程中满足 |val| \le 1000 \val1000 ,字符串长度满足 1 \le n \le 1000 \1n1000

输入描述:

输入一个算术表达式

输出描述:

得到计算结果

思路把中缀表达式转为后缀表达式

但现在的难点在于:如何把中缀表达式转成后缀表达式?

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

  1. 初始化两个栈:
  • 运算符栈:s1
  • 中间结果栈:s2
  1. 从左到右扫描中缀表达式
  2. 遇到操作数时,将其压入 s2
  3. 遇到运算符时比较 它 与 s1 栈顶运算符的优先级:再重复第 4.1 步骤,与新的栈顶运算符比较(因为 4.3 将 s1 栈顶运算符弹出了)这里重复的步骤在实现的时候有点难以理解,下面进行解说:
  1. 如果 s1 为空,或则栈顶运算符号为 ( ,则将其压入符号栈 s1
  2. 如果:优先级比栈顶运算符 ,也将其压入符号栈 s1
  3. 如果:优先级比栈顶运算符 低 或 相等,将 s1 栈顶的运算符 弹出,并压入到 s2 中
  4. 如果 s1 栈顶符号 优先级比 当前符号 高或则等于,那么就将其 弹出,压入 s2 中(循环做,是只要 s1 不为空)如果栈顶符号为 (,优先级是 -1,就不会弹出,就跳出循环了
  5. 跳出循环后,则将当前符号压入 s1
  1. 遇到括号时:
  1. 如果是左括号 ( :则直接压入 s1
  2. 如果是右括号 )则依次弹出 s1 栈顶的运算符,并压入 s2,直到遇到 左括号 为止,此时将这一对括号 丢弃
  1. 重复步骤 2 到 5,直到表达式最右端
  2. 将 s1 中的运算符依次弹出并压入 s2
  3. 依次弹出 s2 中的元素并输出,结果的 逆序 即为:中缀表达式转后缀表达式

下面进行举例说明:

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


扫描到的元素 s2 (栈底 -> 栈顶) s1(栈底 -> 栈顶) 说明
1 1 遇到操作数,将其压入 s2
+ 1 + s1 栈为空,将其压入 s1
( 1 + ( 是左括号,压入 s1
( 1 + ( ( 是左括号,压入 s1
2 1 2 + ( ( 遇到操作数,将其压入 s2
+ 1 2 + ( ( + 遇到操作符:与 s1 栈顶运算符比较,为 (,将其压入 s1
3 1 2 3 + ( ( + 遇到操作数,将其压入 s2
) 1 2 3 + + ( 遇到右括号:弹出 s1 中的 + 压入 s2 中,这里去掉这一对小括号
* 1 2 3 + + ( * 遇到操作符:与 s1 栈顶比较,为 (,将其压入 s1 栈
4 1 2 3 + 4 + ( * 遇到操作数:将其压入 s2
) 1 2 3 + 4 * + 遇到右括号:弹出 s 1 中的 * 压入 s2 中,这里去掉这一队小括号
- 1 2 3 + 4 * + - 遇到操作符:与 s1 栈顶比较,优先级一致,将 s1 中的 + 弹出,并压入 s2 中
5 1 2 3 + 4 * + 5 - 遇到操作数:将其压入 s2

1 2 3 + 4 * + 5 - 解析完毕,将 s1 中的符号弹出并压入 s2 中

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

一个疑问

老师,你怎么知道这个中缀表达式转后缀表达式的思路是这样的?

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

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

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

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

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        List<String> infix = expressionToList(s);  // List
        List<String> suffix = infixToSuffix(infix); // 中缀转后缀
        Stack<String> stk = new Stack<>();    // 存储中间结果
        // 逆波兰计算器
        for (int i = 0; i < suffix.size(); i++) {
            String tmp = suffix.get(i);
            if (isOper(tmp)) {
                String num2 = stk.pop();
                String num1 = stk.pop();
                String reuslt = cal(num1, tmp, num2);
                stk.push(reuslt);
            } else { // 数字直接入栈
                stk.push(tmp);
            }
        }
        System.out.println(stk.pop());
    }
    public static String cal(String num1, String oper, String num2) {
        Long result = 0l;
        Long a = Long.parseLong(num1);
        Long b = Long.parseLong(num2);
        switch (oper) {
            case "+":
                result = a + b;
                break;
            case "-":
                result = a - b;
                break;
            case "*":
                result = a * b;
                break;
            case "/":
                result = a / b;
                break;
        }
        return String.valueOf(result);
    }
    public static List<String> infixToSuffix(List<String> infix) {
        List<String> suffix = new ArrayList<>();
        Stack<String> stack1 = new Stack<>();   // 只用于保存操作符
        Stack<String> stack2 = new Stack<>();   // 用于保存中间结果
        for (int i = 0; i < infix.size(); i++) {
            String tmp = infix.get(i);
            if (!isOper(tmp)) {
                stack2.push(tmp);
            } else if (stack1.isEmpty() || "(".equals(tmp) || "[".equals(tmp) || "{".equals(tmp)) {
                // 如果 stack1 是空的,或者 tmp 是左括号,直接入栈
                stack1.push(tmp);
            } else if (")".equals(tmp) || "]".equals(tmp) || "}".equals(tmp)) {
                // tmp 是右括号,则把 stack1 遇到左括号之前,全部倒入 stack2
                while (!("(".equals(stack1.peek()) || "[".equals(stack1.peek()) || "{".equals(stack1.peek()))) {
                    stack2.push(stack1.pop());
                }
                stack1.pop();   // 丢掉左括号
            }
            // 剩下的则是运算符
            else {
                // 如果 s1 为空,或则栈顶运算符为 (,则压入符号栈 s1
                // 如果优先级比栈顶运算符 高,则压入符号栈 s1,否则,否则将 s1 栈顶的运算符弹出,压入 s2 中
                // 上面两句话,转换成下面的描述
                // 上面如果  s1 栈顶符号优先级比 当前符号高,则弹出加入到 s2 中。
                // 因为:如果栈顶符号是 ( 返回优先级为 -1.比当前符号低,则不会走该方法
                while (!stack1.isEmpty() && priority(stack1.peek()) >= priority(tmp)) {
                    stack2.push(stack1.pop());
                }
                stack1.push(tmp);
            }
        }
        // stack1 剩余操作符全部倒入 stack2
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        // stack2 的逆序才是结果,所以要再倒一次
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        // 现在 stack1 的元素倒出来的顺序就是后缀表达式
        while (!stack1.isEmpty()) {
            suffix.add(stack1.pop());
        }
        return suffix;
    }
    public static List<String> expressionToList(String expression) {
        List<String> list = new ArrayList<>();
        int len = expression.length();
        String keepNum = "";
        for (int i = 0; i < len; i++) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                if (i != len - 1 && Character.isDigit(expression.charAt(i + 1))) {
                    // 如果下一个字符也是数字
                    keepNum += c;
                } else {
                    // 当前是最后一个字符,或者下一个开始不是数字
                    keepNum += c;
                    list.add(keepNum);
                    keepNum = "";
                }
            } else if (c == '-') {
                if (i == 0 || expression.charAt(i - 1) == '(' || expression.charAt(i - 1) == '[' || expression.charAt(i - 1) == '{') {
                    keepNum += c;
                } else {
                    list.add(c + "");
                }
            } else {
                list.add(c + "");
            }
        }
        return list;
    }
    public static boolean isOper(String str) {
        return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str) ||
                "(".equals(str) || ")".equals(str) || "[".equals(str) || "]".equals(str) ||
                "{".equals(str) || "}".equals(str);
    }
    public static int priority(String oper) {
        if ("+".equals(oper) || "-".equals(oper)) {
            return 0;
        } else if ("*".equals(oper) || "/".equals(oper)) {
            return 1;
        } else {
            return -1;
        }
    }
}

















































































































































         
相关文章
|
5月前
|
C语言
数据结构------栈(Stack)和队列(Queue)
数据结构------栈(Stack)和队列(Queue)
37 0
|
7月前
|
存储
数据结构——栈(Stack)
栈(Stack)是一种常见且重要的数据结构,它遵循后进先出(Last-In-First-Out, LIFO)的原则,即最后加入的元素会是第一个被移除的。
96 4
|
9月前
|
存储 人工智能 程序员
技术心得记录:堆(heap)与栈(stack)的区别
技术心得记录:堆(heap)与栈(stack)的区别
63 0
|
9月前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
存储 canal 算法
数据结构之Stack | 让我们一块来学习数据结构
数据结构之Stack | 让我们一块来学习数据结构
71 0
|
10月前
|
存储
【数据结构】栈(Stack)的实现 -- 详解
【数据结构】栈(Stack)的实现 -- 详解
|
测试技术 C语言
[数据结构 -- C语言] 栈(Stack)
[数据结构 -- C语言] 栈(Stack)
|
10月前
|
算法 安全 Java
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
57 0
|
10月前
数据结构 模拟实现Stack栈(数组模拟)
数据结构 模拟实现Stack栈(数组模拟)
82 0
递归工作栈(Recursive Workstation Stack)
递归工作栈(Recursive Workstation Stack)是一种在计算机程序中实现递归计算的机制,通过使用栈来跟踪递归调用的过程,从而实现对复杂问题的求解。递归工作栈在解决具有自相似结构的问题时非常有用,例如计算斐波那契数列、解决迷宫问题等。
328 9