ALGO-156表达式计算

最新推荐文章于 2024-09-07 08:58:50 发布

AC_coding

最新推荐文章于 2024-09-07 08:58:50 发布

阅读量521

点赞数

分类专栏：蓝桥OJ 文章标签： java 算法

本文链接：https://blog.csdn.net/Morandas/article/details/70312522

版权

蓝桥OJ 专栏收录该内容

10 篇文章

订阅专栏

本文介绍了一种通过转换中缀表达式为后缀表达式，并计算后缀表达式的值来解决四则运算问题的方法。包括算法实现的详细步骤及Java代码示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：

问题描述

　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。

输入格式

　　输入一行，包含一个表达式。

输出格式

　　输出这个表达式的值。

样例输入

1-2+3*(4-5)

样例输出

-4

数据规模和约定

　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

刚开始直接按照思维逻辑做，先求括号运算，再四则运算，结果各种bug不断

预备知识：

中缀表达式：

平时所用的标准四则运算表达式，如 1+((23+34)*5)-6 叫做中缀表达式，因为所有的运算符号都在两数字的中间。

后缀表达式：

不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如 1 23 34+5*+6-，即 1+((23+34)*5)-6

中缀表达式转后缀表达式的方法：

1，开栈res，遍历中缀表达式

2，遇到数字，直接输出（注意>10的数字的处理）

3，遇到操作符

3.1 运算符

3.11 栈为空，直接入栈

3.12 栈不为空，依次弹出栈中所有优先级大于等于该运算符的栈顶元素并输出，再将该运算符入栈 (*/>+-)

3.2 括号

3.21 （，入栈

3.22 ），依次弹出栈顶元元素并输出，直到弹出的是（，（不输出

4，将栈中剩余元素依次输出

输出结果即为后缀表达式

例子：

1+((23+34)*5)-6

栈res（栈底----栈顶）	遍历元素【步骤】	输出结果
null	1(输出)【2】	1
+	+（入栈）【3.1】	1
+（	（（入栈）【3.21】	1
+（（	（（入栈）【3.21】	1
+（（	23（输出）【2】	1 23
+（（+	+（入栈）【3.12】	1 23
+（（+	34（输出）【2】	1 23 34
+（	）（出栈）【3.22】	1 23 34+
+（*	*（入栈）【3.12】	1 23 34+
+（*	5（输出）【2】	1 23 34+5
+	）（出栈并输出）【3.22】	1 23 34+5*
-	-（出栈并输出后入栈）【3.12】	1 23 34+5*+
-	6（输出）【2】	1 23 34+5*+6
null	剩余元素输出【4】	1 23 34+5*+6-

后缀表达式的求值方法：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
1 23 34+5*+6- ：

(1) 从左至右扫描，将1，23，34压入堆栈（1,23,34）；
(2) 遇到+运算符，因此弹出34和23（34为栈顶元素，23为次顶元素），计算出34+23的值，得57，再将57入栈（1,57）；
(3) 将5入栈（1,57,5）；
(4) 接下来是 * 运算符，因此弹出5和57，计算出5×57=285，将285入栈（1,285）；
(5) 接下来是 + 运算符，因此弹出5和57，计算出285+1=286，将286入栈（286）；

(6) 将6入栈（286,6）；
(7) 最后是-运算符，计算出286-6的值，即280。

  // 运算次序是反的,跟入栈出栈次序有关
    public static int cal(int m, int n, char c) {
        if (c == '+') {
            return n + m;
        } else if (c == '-') {
            return n - m;
        } else if (c == '*') {
            return n * m;
        } else{
            return n / m;
        }
    }

实际操作是开两个栈，一个存储数字，一个存储符号

import java.util.Scanner;
import java.util.Stack;

public class algo_156_temp {
    public static void main(String[] args) {
    	
        Scanner sc = new Scanner(System.in);
        Stack<Integer> nums = new Stack<Integer>(); // 保存数字
        Stack<Character> opes = new Stack<Character>(); // 保存操作符
        String string = sc.nextLine();
        int n = 0; // 保存每一个数字
        char[] cs = string.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            char temp = cs[i];
            if (Character.isDigit(cs[i])) {
                n = 10 * n + Integer.parseInt(String.valueOf(cs[i])); // 大于10的数字保存
            } else {
                if (n != 0) {
                    nums.push(n);
                    n = 0;
                }
                if (temp == '(') {
                    opes.push(temp);
                } else if (temp == ')') {
                    while (opes.peek() != '(') { // 括号里面运算完
                        int t = cal(nums.pop(), nums.pop(), opes.pop());
                        nums.push(t);
                    }
                    opes.pop();
                } else if (priority(temp) > 0) {
                    if (opes.isEmpty()) { // 栈为空直接入栈
                        opes.push(temp);
                    } else {
                        // 若栈顶元素优先级大于或等于要入栈的元素,将栈顶元素弹出并计算,然后入栈
                        if (priority(opes.peek()) >= priority(temp)) {
                            int t = cal(nums.pop(), nums.pop(), opes.pop());
                            nums.push(t);
                        }
                        opes.push(temp);
                    }
                }
            }
        }
        // 最后一个字符若是数字,未入栈
        if (n != 0) {
            nums.push(n);
        }
        while (!opes.isEmpty()) {
            int t = cal(nums.pop(), nums.pop(), opes.pop());
            nums.push(t);
        }
        System.out.println(nums.pop());
    }

    // 返回的是运算符的优先级,数字和()不需要考虑
    public static int priority(char c) {
        if (c == '+' || c == '-') {
            return 1;
        } else if (c == '*' || c == '/') {
            return 2;
        } else {
            return 0;
        }
    }

    // 运算次序是反的,跟入栈出栈次序有关
    public static int cal(int m, int n, char c) {
        if (c == '+') {
            return n + m;
        } else if (c == '-') {
            return n - m;
        } else if (c == '*') {
            return n * m;
        } else{
            return n / m;
        }
    }
}