精华内容
下载资源
问答
  • 所以我们就只要以i为中心,找到左边和右边第一小于nums[i]的元素,找到边界后我们的答案是nums[i]乘以区间和,我们可以用前缀和来计算区间和,这就是以nums[i]为最小值的最大乘积了。我们只要枚举nums数组所有

    题目链接:https://leetcode-cn.com/problems/maximum-subarray-min-product/

    解题思路

    方法一:JAVA栈

    我们可以发现,如果以nums[i]为最小值,那我们怎么找到最大乘积,因为所有数都是大于0的,所有我们区间越大,则答案越大。所以我们就只要以i为中心,找到左边和右边第一个小于nums[i]的元素,找到边界后我们的答案是nums[i]乘以区间和,我们可以用前缀和来计算区间和,这个就是以nums[i]为最小值的最大乘积了。我们只要枚举nums数组所有元素一遍就可以求出最大值,下面就是java栈的代码。

    代码

    class Solution {
        static int N = 100010;
        static int[] h = new int[N];    //原数组
        static int[] l = new int[N];    //左边的最小值栈
        static int[] r = new int[N];    //右边的最小值栈
        static long[] s = new long[N];  //前缀和数组
        public int maxSumMinProduct(int[] nums) {
            int n = nums.length;
            for (int i = 1; i <= n; i ++ ) {    //计算前缀和
                h[i] = nums[i - 1]; //原数组往后移动一位,加哨兵
                s[i] = s[i - 1] + h[i]; //计算前缀和
            }
            h[0] = 0;   //最前面的哨兵,方便左边栈的统一处理
            h[n + 1] = 0;   //最后面的哨兵,方便右边栈的统一处理
            Deque<Integer> stack = new LinkedList<>();  //左边最小值栈
            stack.push(0);  //放哨兵我们栈存储的是下标
            for (int i = 1; i <= n; i ++ ) {    //找到h[i]左边界
                while (h[i] <= h[stack.peek()])     //如果当前栈顶大于等于当前元素则出栈
                    stack.pop();
                l[i] = stack.peek();    //记录i左边第一个比i小的数
                stack.push(i);  //将i入栈
            }
            Deque<Integer> stack1 = new LinkedList<>(); //右边最小值栈
            stack1.push(n + 1);     //放哨兵
            for (int i = n; i != 0; i -- ) {    //找到h[i]右边界,从右往左遍历
                while (h[i] <= h[stack1.peek()]) //如果当前栈顶大于等于当前元素则出栈
                    stack1.pop();
                r[i] = stack1.peek();   //记录i右边第一个比i小的数
                stack1.push(i); //将i入栈
            }
            long res = 0;
            for (int i = 1; i <= n; i ++ )  //以当前元素h[i]为最小值的最大乘积
                res = Math.max(res, h[i] * (s[r[i] - 1] - s[l[i]]));    //最小元素乘以区间和
            return (int)(res % 1000000007L);
        }
    }
    

    复杂度分析

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    方法二:数组模拟栈

    对于acm选手来说一般要追求时间效率,所以一般都是自己用数组模拟栈,虽然时间复杂度没变,但是这样比直接用java栈速度快很多。思路都是一样的

    代码

    class Solution {
        static int N = 100010;
        static int[] h = new int[N];    //原数组
        static int[] l = new int[N];    //左边的最小值栈
        static int[] r = new int[N];    //右边最小值栈
        static int[] q = new int[N];    //栈
        static long[] s = new long[N];  //前缀和数组
        public int maxSumMinProduct(int[] nums) {
            int n = nums.length;
            for (int i = 1; i <= n; i ++ ) {
                h[i] = nums[i - 1]; //原数组往后移动一位
                s[i] = s[i - 1] + h[i]; //计算前缀和
            }
            h[0] = 0;   //最前面的哨兵
            h[n + 1] = 0;   //最后面的哨兵
            int tt = 0; //指向栈顶元素
            q[0] = 0;
            for (int i = 1; i <= n; i ++ ) {    //找到h[i]左边界
                while (h[i] <= h[q[tt]])  //如果当前元素比栈顶小,弹栈
                    tt--;
                l[i] = q[tt];   //记录h[i]的左边界
                q[++tt] = i;  //把i压入栈
            }
            tt = 0;
            q[0] = n + 1;
            for (int i = n; i != 0; i -- ) {    //找到h[i]右边界
                while (h[i] <= h[q[tt]]) //如果当前元素比栈顶小,弹栈
                    tt -- ;
                r[i] = q[tt];   //记录h[i]的右边界
                q[++tt] = i;    //把i压入栈
            }
            long res = 0;
            for (int i = 1; i <= n; i ++ )  //以当前元素为最小值的最大乘积
                res = Math.max(res, h[i] * (s[r[i] - 1] - s[l[i]]));    //最小元素乘以区间和
            return (int)(res % 1000000007L);
        }
    }
    

    复杂度分析

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)
    展开全文
  • 如上图所示,我们看这代码分析首先,单调必须保证单调对吧,所以说我们将大于栈顶元素的元素入栈,直到遇到一小于栈顶元素的,然后因为是单调,所以我们想让它入栈,就必须删除中比他大的元素,但是又要不...


    如上图所示,我们看这代码分析

    首先,单调栈必须保证单调对吧,所以说我们将大于栈顶元素的元素入栈,直到遇到一个小于栈顶元素的数,然后因为是单调栈,所以我们想让它入栈,就必须删除栈中比他大的元素,但是又要不影响结果,所以每个栈顶元素出栈是都要计算它与前面出栈元素组成的最大矩形,直到在栈中找到一个比待入栈元素小的数。然后插入到它的旁边。

    有的人可能会问,这怎么不会使结果变化呢?,因为我们,出栈时已经计算了前面最大的值出来,所以后面的数在入栈时同样结果不变。

    推荐手动模拟一下,下图没模拟完


    image

      1 #include <iostream>
      2 #include <algorithm>
      3 using namespace std;
      4 const int N = 1e5 + 5;
      5 
      6 using ll = long long;
      7 
      8 ll a[N], s[N], w[N];
      9 
     10 ll ans;
     11 int n, p;
     12 int main() {
     13 	while(cin >> n, n) {
     14 		ans = 0, p = 0;
     15 
     16 		for(int i = 1; i <= n; ++ i) cin >> a[i];
     17 		a[n+1] = 0;
     18 		for (int i = 1; i <= n + 1; ++ i) {
     19 			if (a[i] > s[p]) s[++p] = a[i] , w[p] = 1;//单调入栈
     20 			else {
     21 				int width = 0;
     22 				while(s[p] > a[i]) {//将栈顶元素和要入栈的元素相比,大的出栈;
     23 					width += w[p];//加上宽度
     24 					ans = max(ans, (ll)width * s[p]);//每次计算面积最大值
     25 					p--;//出栈
     26 				}
     27 				s[++p] = a[i], w[p] = width + 1;//将其入栈,这是不边的关键代码
     28 
     29 			}
     30 		}
     31 		cout << ans << endl;
     32 	}
     33 }
    展开全文
  • 一个计算器简单实现,计算机怎么理解算式,对于计算机而言,他接受到就是一个字符串,而且不是两个数之间,而是一串算式计算 你就得考虑拆分数字和运算符,你还得考虑计算优先级等等 引出栈介绍 什么是 ...

    问题引入

    一个计算器的简单实现,计算机怎么理解算式的,对于计算机而言,他接受到的就是一个字符串,而且不是两个数之间,而是一串算式计算

    你就得考虑拆分数字和运算符,你还得考虑计算优先级等等

    引出栈的介绍

    什么是栈

    1)栈的英文为(stack)
    2)栈是一个先入后出(FILO-First In Last Out)的有序列表
    3)栈(stack)是 限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top)另一端为固定的一端, 称为栈底(Bottom)
    4)根据栈的定义可知,最先放入栈中元素在栈底最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除

    在这里插入图片描述

    应用场景

    • 子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中。类似我们的retrun语句
    • 处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数、区域变量等数据存入堆栈中。
    • 表达式的转换**(中缀表达式转后缀表达式)**与求值(实际解决)。
    • 二叉树的遍历。
    • 图形的深度优先(depth- first)搜索法

    数组模拟栈的思路

    1.定义一个top来表示我们的栈顶,初始化为-1

    2.当有数据加入到栈时,top++,数据stack[top] = data;

    3.出栈操作,int value = stack[top]; top–; return value;

    栈满的情况:top = maxSize -1;

    栈空的情况:top = -1;

    代码实现

    /**
     * @author 王庆华
     * @version 1.0
     * @date 2020/12/15 20:09
     * @Description TODO
     * @pojectname 算法代码
     */
    public class ArrayStackDemo {
        public static void main(String[] args) {
            //测试
            //创建ArrayStack对象
            ArrayStack stack = new ArrayStack(4);
            String key = "";
            boolean loop = true;//是否退出菜单
            Scanner scanner = new Scanner(System.in);
            while (loop){
                System.out.println("show:显示栈");
                System.out.println("exit:退出程序");
                System.out.println("push:入栈");
                System.out.println("pop:出栈");
                System.out.println("输入你的选择");
                key = scanner.next();
                switch (key){
                    case "show":{
                        stack.list();
                        break;
                    }
                    case "push":{
                        System.out.println("请输入你入栈的数值");
                        int value = scanner.nextInt();
                        stack.push(value);
                        break;
                    }
                    case "pop":{
                        try {
                            int reslut = stack.pop();
                            System.out.println("出栈的数据是"+reslut);
                        }catch (Exception e){
                            e.getMessage();
                        }
                        break;
                    }
                    case "exit":{
                        scanner.close();
                        loop = false;
                        break;
                    }
                }
            }
            System.out.println("程序退出了");
    
        }
    }
    
    
    //顶一个ArrayStack 表示我们的栈
    class ArrayStack{
        private int maxSize;//栈的大小
        private int[] stack;//数组模拟栈,数据存储在该数组中
        private int top = -1; //表示栈顶    初始化为-1
    
        //构造器
        public ArrayStack(int maxSize){
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
    
        //判断栈满
        public boolean isFull(){
            return top == maxSize-1;
        }
        //栈空
        public boolean isEmpty(){
            return top == -1;
        }
        //入栈
        public void push(int value){
            //判断栈是否满
            if (isFull()){
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }
        //出栈    将栈顶的数据返回
        public int pop(){
            if (isEmpty()){
                //抛出异常
                throw new RuntimeException("栈为空,无法出栈");
            }
            int value = stack[top];
            top--;
            return value;
        }
        //遍历栈   从栈顶向下遍历
        public void list(){
            if (isEmpty()){
                System.out.println("栈空,没有数据");
                return;
            }
            for (int i = top;i>=0;i--){
                System.out.println("索引是"+i+"值为"+stack[i]);
            }
        }
    
    }
    

    单链表实现栈

    package com.wang.stack;
    
    import java.util.Scanner;
    import java.util.Stack;
    
    /**
     * @author 王庆华
     * @version 1.0
     * @date 2020/12/15 20:29
     * @Description TODO
     * @pojectname 算法代码
     */
    public class LinkedStackDemo {
        public static void main(String[] args) {
            LinkedListStack stack = new LinkedListStack();
            String key = "";
            boolean loop = true;
            Scanner scanner = new Scanner(System.in);
            while (loop) {
                System.out.println("show: 表示显示栈");
                System.out.println("push:  表示添加数据到栈(入栈)");
                System.out.println("pop:  表示从栈取出数据(出栈)");
                System.out.println("length:  表示栈有多少个数据");
                System.out.println("top:  表示栈顶的值");
                System.out.println("exit: 退出程序");
                System.out.println("请输入你的选择");
                key = scanner.next();
                switch (key) {
                    case "show":
                        stack.list();
                        break;
                    case "push":
                        System.out.println("请输入一个数");
                        int value = scanner.nextInt();
                        stack.push(value);
                        break;
                    case "pop":
                        try {
                            Object res = stack.pop();
                            System.out.println("出栈的数据是:" + res);
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "length":
                        int length = stack.getLength();
                        System.out.println("栈有" + length + "个数据");
                        break;
                    case "top":
                        try {
                            Object top = stack.top();
                            System.out.println("栈顶为:" + top);
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "exit":
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
        }
    
    }
    
    class LinkedListStack {
        ListStack head = new ListStack(null);//初始化节点
        //判断空
        public boolean isEmpty() {
            return head.getData() == null;
        }
        //入栈
        public void push(Object value) {
            if (head.getData() == null) {
                head.setData(value);
            } else {
                ListStack newStack = new ListStack(value);//新增节点
                newStack.setNext(head);//新增节点的下一个节点是上一个节点
                head = newStack;//头结点变回开始位置
            }
        }
        //出栈
        public Object pop() {
            Object data = null;
            if (isEmpty()) {
                throw new RuntimeException("栈空");
            }
            data = head.getData();
            //原来的节点出去了,现在的头结点是原来的下一个节点
            head = head.getNext();
            return data;
        }
        //展示我们的链表实现的栈
        public void list() {
            if (isEmpty()) {
                System.out.println("栈空");       
            }
            ListStack temp = head;//辅助指针
            while (temp!= null) {//还有元素
                System.out.println(temp.getData());
                temp = temp.getNext();//后移以为继续输出
            }
        }
        //取栈顶,但是不删除
        public Object top() {
            Object data = null;
            if (isEmpty()) {
                throw new RuntimeException("栈空");
            }
            data = head.getData();
            return data;
        }
        //获取栈的长度
        public int getLength() {
            int count = 0;
            ListStack temp = head;
            if (isEmpty() || temp.getData() == null) {
                return 0;
            } else {
                while (temp != null) {
                    count++;
                    temp = temp.getNext();
                }
            }
            return count;
        }
    
    }
    
    class ListStack {
        private Object data;//存储数据
        private ListStack next;//指向下一个节点
    
        public ListStack(Object data) {
            this.data = data;
        }
    
        public Object getData() {
            return data;
        }
    
        public void setData(Object data) {
            this.data = data;
        }
    
        public ListStack getNext() {
            return next;
        }
    
        public void setNext(ListStack next) {
            this.next = next;
        }
    }
    

    问题解决 使用栈完成计算表达式结果

    思路分析

    数栈:存放数据 numStack

    符号栈:存放符号位 operStack

    1.通过一个index值(可以认为是索引)来遍历表达式

    2.如果我们发现index扫描到的位置是数字,就直接入数栈

    3.如果发现扫描到的是一个符号,分如下情况来解决

    ​ 如果发现当前符号栈为空,就直接入栈

    如果符号栈不为空(有操作符),就进行比较,如果当前的操作符的优先级小于或等于栈中的操作符,就需要从数栈中pop出两个数,再从符号栈中pop出一个符号进行运算,将得到的结果在入数栈,然后将当前的操作符入符号栈

    ​ 如果符号栈不为空(有操作符)且当前扫描到的运算优先级大于栈中的操作符,直接入符号栈

    4.扫描完毕过后,就顺序的从数栈和符号栈中pop出相应的数和符号并运算

    5.最后在数栈中只有一个数字,就表示结果

    代码 中缀表达式

    package com.wang.stack;
    
    /**
     * @author 王庆华
     * @version 1.0
     * @date 2020/12/18 21:41
     * @Description TODO
     * @pojectname 算法代码 计算器
     */
    public class Calculator {
            public static void main(String[] args) {
                //构建表达式
                String expression = "3+2*6-2";
                //创建两个栈一个数栈,一个符号栈
                ArrayStack2 numStack = new ArrayStack2(10);
                ArrayStack2 operStack = new ArrayStack2(10);
                //定义需要的相关变量
                int index = 0;  //用于帮助我们扫描
                int num1 = 0;
                int num2 = 0;
                int oper = 0;   //扫描到的操作符
                int res = 0;    //结果
                char ch = ' ';  //扫描到的字符
                //开始循环扫描
                while (true){
                    //依次得到expression的每一个字符
                    ch = expression.substring(index,index+1).charAt(0);//拿到一个字符
                    //判断ch是什么
                    if (operStack.isOper(ch)){
                        //判断当前的符号栈是否为空
                        if (!operStack.isEmpty()){
                            //不为空
                            //比较优先级
                            if (operStack.priority(ch)<=operStack.priority(operStack.pick())){
                                num1 = numStack.pop();
                                num2 = numStack.pop();
                                oper = operStack.pop();
                                res = numStack.cal(num1,num2,oper);
                                //运算结果入栈
                                numStack.push(res);
                                //当前运算符入符号栈
                                operStack.push(ch);
                            }else {
                                //如果符号栈不为空(有操作符)且当前扫描到的运算优先级大于栈中的操作符,直接入符号栈
                                operStack.push(ch);
                            }
                        }else
                        {
                            //符号栈为空,直接入栈
                            operStack.push(ch);
                        }
                    }else {
                        //如果是数字,则直接入数栈
                        numStack.push(ch-48);//ch是作为字符传入的 1 对应的是49 3 对应的是51,相差48,我们要减去48
                    }
                    //idnex+1,判断是否到我们字符串表达式的最后
                    index++;
                    if (index>= expression.length()){
                        break;
                    }
                }
    
                //遍历完了我们的字符串表达式
                while (true){
                    //如果我们的符号栈为空,说明我们结算到了最后的结果,数栈只有结果一个数字
                    if (operStack.isEmpty()){
                        break;
                    }
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    oper = operStack.pop();
                    res = numStack.cal(num1,num2,oper);
                    numStack.push(res);
                }
                System.out.println("表达式结果是:"+numStack.pop());
            }
    }
    //拿了我们以前的数组实现栈的代码
    //顶一个ArrayStack 表示我们的栈
    //但是我们要增加一些功能       如判断优先级等等
    class ArrayStack2{
        private int maxSize;//栈的大小
        private int[] stack;//数组模拟栈,数据存储在该数组中
        private int top = -1; //表示栈顶    初始化为-1
    
        //构造器
        public ArrayStack2(int maxSize){
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
    
        //判断栈满
        public boolean isFull(){
            return top == maxSize-1;
        }
        //栈空
        public boolean isEmpty(){
            return top == -1;
        }
        //入栈
        public void push(int value){
            //判断栈是否满
            if (isFull()){
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }
        //出栈    将栈顶的数据返回
        public int pop(){
            if (isEmpty()){
                //抛出异常
                throw new RuntimeException("栈为空,无法出栈");
            }
            int value = stack[top];
            top--;
            return value;
        }
        //遍历栈   从栈顶向下遍历
        public void list(){
            if (isEmpty()){
                System.out.println("栈空,没有数据");
                return;
            }
            for (int i = top;i>=0;i--){
                System.out.println("索引是"+i+"值为"+stack[i]);
            }
        }
        //返回运算符的优先级,优先级使用数字来表示
        //数值越大,则优先级越高
        public int priority(int oper){
            if (oper == '*'|| oper == '/'){
                return 1;
            }else if (oper == '+' || oper == '-'){
                return 0;
            }else {
                return -1;//假设目前的表达式只有+-*/
            }
        }
        //判断是不是运算符
        public boolean isOper(char var){
            return var == '+' || var == '-' || var == '*' || var == '/';
        }
        //返回当前栈顶的值,但不是真正的出栈
        public int pick(){
            return stack[top];
        }
        //计算方法
        public int cal(int num1,int num2,int oper){ //int  char是能进行互换的
            int res = 0; // 用于存放计算的结果
            switch (oper){
                case '+':{
                    res = num1+num2;
                    break;
                }
                case '-':{
                    res = num2 - num1;
                    break;
                }
                case '*':{
                    res = num1 * num2;
                    break;
                }
                case '/':{
                    res = num2/num1;
                    break;
                }
                default:
                    break;
            }
            return res;
        }
    
    }
    

    缺点 问题

    我们发现我们这样数字小一点计算没有问题,但是如果我们的数字较大,会出现什么问题呢?

    例如我们80+2*6-4应该等于88 可结果输出:表达式结果是:8

    同样的70+2*6-4应该等于78 可输出结果是 表达式结果是:8

    是不是有数字超过了10位数,我们计算的时候省略了那个10位数的数字呢?

    我们试一试11+2*6-4 结果应该等于19 输出结果是:表达式结果是:9

    难道真的是11变成了1进去运算了么?还是说我们ascii码中只有0~9的对应值大于9的字符都没了?

    问题解决

    我们大概率能知道,这个问题出在我们的数字入栈上,我们数字入栈的操作是这样的

    else {
        //如果是数字,则直接入数栈
        numStack.push(ch-48);//ch是作为字符传入的 1 对应的是49 3 对应的是51,相差48,我们要减去48
    }
    

    它是一位一位扫描的,两位数只会扫进去一个,也就是我们的问题出在数字入栈上

    解决思路:

    1.当处理多位数时,不能发现是一个数就立即入栈,有可能是多位数,我们得判断下面的字符是什么

    2.处理数是,向后一位index+1判断,是不是数,是符号则入栈,如果是数字,则要进行拼接

    3.定义一个字符串变量,用于多位数的时候进行拼接

    代码:

    else {
        //处理多位数
        keepNum += ch;
        //判断下一个字符是不是数字,是数字继续扫描,运算符,则入栈
        if (operStack.isOper(expression.substring(index+1,index+2).charAt(0)))
        {
            //后面是运算符,怎入栈
            numStack.push(Integer.parseInt(keepNum));
            //将我们的keepNum清空
            keepNum = "";
        }
        numStack.push(ch-48);//ch是作为字符传入的 1 对应的是49 3 对应的是51,相差48,我们要减去48
    
    }
    

    运行发现:

    Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 9
    	at java.lang.String.substring(String.java:1963)
    	at com.wang.stack.Calculator.main(Calculator.java:57)
    

    数组越界?为什么呢?因为我们少考虑了当前的ch如果是最后一位呢?,index还能往后+么,显然是不能的

    //处理多位数
    keepNum += ch;
    //如果ch已经是字符串表达式最后一位
    if (index == expression.length() -1)
    {
        numStack.push(Integer.parseInt(keepNum));
    }
    else {
        //判断下一个字符是不是数字,是数字继续扫描,运算符,则入栈
        if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
            //后面是运算符,怎入栈
            numStack.push(Integer.parseInt(keepNum));
            //将我们的keepNum清空
            keepNum = "";
        }
    }
    

    最终代码

    package com.wang.stack;
    
    /**
     * @author 王庆华
     * @version 1.0
     * @date 2020/12/18 21:41
     * @Description TODO
     * @pojectname 算法代码 计算器
     */
    public class Calculator {
            public static void main(String[] args) {
                //构建表达式
                String expression = "10+2*6-4";
                //创建两个栈一个数栈,一个符号栈
                ArrayStack2 numStack = new ArrayStack2(10);
                ArrayStack2 operStack = new ArrayStack2(10);
                //定义需要的相关变量
                int index = 0;  //用于帮助我们扫描
                int num1 = 0;
                int num2 = 0;
                int oper = 0;   //扫描到的操作符
                int res = 0;    //结果
                char ch = ' ';  //扫描到的字符
                String keepNum = "";//用于拼接字符串
                //开始循环扫描
                while (true){
                    //依次得到expression的每一个字符
                    ch = expression.substring(index,index+1).charAt(0);//拿到一个字符
                    //判断ch是什么
                    if (operStack.isOper(ch)){
                        //判断当前的符号栈是否为空
                        if (!operStack.isEmpty()){
                            //不为空
                            //比较优先级
                            if (operStack.priority(ch)<=operStack.priority(operStack.pick())){
                                num1 = numStack.pop();
                                num2 = numStack.pop();
                                oper = operStack.pop();
                                res = numStack.cal(num1,num2,oper);
                                //运算结果入栈
                                numStack.push(res);
                                //当前运算符入符号栈
                                operStack.push(ch);
                            }else {
                                //如果符号栈不为空(有操作符)且当前扫描到的运算优先级大于栈中的操作符,直接入符号栈
                                operStack.push(ch);
                            }
                        }else
                        {
                            //符号栈为空,直接入栈
                            operStack.push(ch);
                        }
                    }else {
                        //处理多位数
                        keepNum += ch;
                        //如果ch已经是字符串表达式最后一位
                        if (index == expression.length() -1)
                        {
                            numStack.push(Integer.parseInt(keepNum));
                        }
                        else {
                            //判断下一个字符是不是数字,是数字继续扫描,运算符,则入栈
                            if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                                //后面是运算符,怎入栈
                                numStack.push(Integer.parseInt(keepNum));
                                //将我们的keepNum清空
                                keepNum = "";
                            }
                        }
                    }
                    //idnex+1,判断是否到我们字符串表达式的最后
                    index++;
                    if (index>= expression.length()){
                        break;
                    }
                }
    
                //遍历完了我们的字符串表达式
                while (true){
                    //如果我们的符号栈为空,说明我们结算到了最后的结果,数栈只有结果一个数字
                    if (operStack.isEmpty()){
                        break;
                    }
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    oper = operStack.pop();
                    res = numStack.cal(num1,num2,oper);
                    numStack.push(res);
                }
                System.out.println("表达式结果是:"+numStack.pop());
            }
    }
    //拿了我们以前的数组实现栈的代码
    //顶一个ArrayStack 表示我们的栈
    //但是我们要增加一些功能       如判断优先级等等
    class ArrayStack2{
        private int maxSize;//栈的大小
        private int[] stack;//数组模拟栈,数据存储在该数组中
        private int top = -1; //表示栈顶    初始化为-1
    
        //构造器
        public ArrayStack2(int maxSize){
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
    
        //判断栈满
        public boolean isFull(){
            return top == maxSize-1;
        }
        //栈空
        public boolean isEmpty(){
            return top == -1;
        }
        //入栈
        public void push(int value){
            //判断栈是否满
            if (isFull()){
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }
        //出栈    将栈顶的数据返回
        public int pop(){
            if (isEmpty()){
                //抛出异常
                throw new RuntimeException("栈为空,无法出栈");
            }
            int value = stack[top];
            top--;
            return value;
        }
        //遍历栈   从栈顶向下遍历
        public void list(){
            if (isEmpty()){
                System.out.println("栈空,没有数据");
                return;
            }
            for (int i = top;i>=0;i--){
                System.out.println("索引是"+i+"值为"+stack[i]);
            }
        }
        //返回运算符的优先级,优先级使用数字来表示
        //数值越大,则优先级越高
        public int priority(int oper){
            if (oper == '*'|| oper == '/'){
                return 1;
            }else if (oper == '+' || oper == '-'){
                return 0;
            }else {
                return -1;//假设目前的表达式只有+-*/
            }
        }
        //判断是不是运算符
        public boolean isOper(char var){
            return var == '+' || var == '-' || var == '*' || var == '/';
        }
        //返回当前栈顶的值,但不是真正的出栈
        public int pick(){
            return stack[top];
        }
        //计算方法
        public int cal(int num1,int num2,int oper){ //int  char是能进行互换的
            int res = 0; // 用于存放计算的结果
            switch (oper){
                case '+':{
                    res = num1+num2;
                    break;
                }
                case '-':{
                    res = num2 - num1;
                    break;
                }
                case '*':{
                    res = num1 * num2;
                    break;
                }
                case '/':{
                    res = num2/num1;
                    break;
                }
                default:
                    break;
            }
            return res;
        }
    
    }
    

    问题引入:我们的表达式中要是有括号呢?后缀表达式又是什么样呢?逆波兰计算器又是什么样的呢?我会在下个博客学习笔记写出

    展开全文
  • 思想:遇到数字就入栈,遇到运算符就pop出两个数进行运算然后将结果入栈。最后留下一个栈顶元素即为结果。 可见,实现后缀表达式计算出并不困难。 这里难点是怎么把我们常用中缀表达式转换成后缀表达式: 这里先...

    JAVA实现后缀表达式–>简单计算器(栈)

    预备知识:

    1. 前缀表达式
    2. 中缀表达式
    3. 后缀表达式

    比如 5 * 2 + 3
    前缀表达式 : + * 5 2 3
    中缀表达式:5 * 2 + 3
    后缀表达式:5 2 * 3 +

    计算机中,使用后缀表达式更容易进行计算:
    思想:遇到数字就入栈,遇到运算符就pop出两个数进行运算然后将结果入栈。最后留下一个栈顶元素即为结果。

    可见,实现后缀表达式计算出并不困难。

    这里的难点是怎么把我们常用的中缀表达式转换成后缀表达式:

    这里先说中缀表达式的思想:

    1. 初始化两个栈,运算符栈s1和储存中间结果的栈s2
    2. 从左至右扫描中缀表达式
    3. 遇到操作数时,将其压入s2
    4. 遇到运算符时,比较其与s1栈顶运算符的优先级
      4.1 如果s1为空,或栈顶运算符为左括号 “(” ,则直接将此运算符入s1栈
      4.2 否则,若优先级比s1栈顶运算符的高,也将运算符压入s1
      4.3 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到4.1与s1中新的栈顶运算符相比较
    5. 遇到括号时:
      (1)如果是左括号 “(” 。则直接压入s1
      (2)如果是右括号 “)” 。则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃。
    6. 重复步骤2至5直到遍历完中缀表达式
    7. 将s1中剩余的运算符依次弹出并压入s2

    奉上步骤图,自己体会。【狗头】
    在这里插入图片描述
    在这里插入图片描述

    此时,中缀表达式转后缀表达式已经完成了。随后我们只需要根据后缀表达式的求值进行即可。

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * 后缀表达式:  我们常使用的为中缀表达式  5+3*8
     * 计算机更容易实现的后缀表达式: 3 8 * 5 +
     *
     * 步骤--》1.先将中缀表达式转换成后缀表达式   (将中缀表达式转换成为list集合,通过stack将中缀表达式转换成后缀表达式)
     * 2. 在将后缀表达式进行计算求值
     */
    public class PostfixExpression {
        public static void main(String[] args) {
            String expression = "10*((20+30)*4)-10";
            List<String> centerList = AnalyticExpression(expression); //将中缀表达式转换成list集合
            System.out.println("中缀表达式:"+centerList.toString());
            List<String> postfixList = toPostfixExpression(centerList); //将中缀集合转换成后缀表达式集合
            System.out.println("后缀表达式:"+postfixList.toString());
            int res = calculator(postfixList);
            System.out.println(res);
        }
    
    
        /**
         * 将字符串转换成字符串集合
         *
         * @param expression 传过来的字符串后缀表达式
         * @return 返回的字符串集合
         */
        public static List<String> AnalyticExpression(String expression) {
    
            List<String> list = new ArrayList<>();
            char c;
            String str = "";  //用于拼接多位数
            int i = 0;
            while (i < expression.length()) {
                if ((c = expression.charAt(i)) < 48 || (c = expression.charAt(i)) > 57) {//如果不是数字
                    list.add(c + "");
                    i++;
                } else {
                    str = "";
                    while (i < expression.length() && ((c = expression.charAt(i)) >= 48) && ((c = expression.charAt(i)) <= 57)) {
                        str += c;
                        i++;
                    }
                    list.add(str);
                }
            }
            return list;
        }
    
        /**
         * 将中缀表达式转换成后缀表达式
         * 思路:
         * 1)初始化两个栈,运算符栈s1和储存中间结果的栈s2
         * 2)从左至右扫描中缀表达式
         * 3)遇到操作数时,将其压入s2
         * 4)遇到运算符时,比较其与s1栈顶运算符的优先级
         * 4.1 如果s1为空,或栈顶运算符为左括号 "(" ,则直接将此运算符入s1栈
         * 4.2 否则,若优先级比s1栈顶运算符的高,也将运算符压入s1
         * 4.3 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到4.1与s1中新的栈顶运算符相比较
         * 5)遇到括号时:
         * (1) 如果是左括号 "(" 。则直接压入s1
         * (2) 如果是右括号 ")" 。则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃。
         * 6)重复步骤2至5直到表达式的最右边
         * 7)将s1中剩余的运算符依次弹出并压入s2
         *
         * @param centerList
         * @return
         */
        public static List<String> toPostfixExpression(List<String> centerList) {
            Stack<String> s1 = new Stack<>();
            Stack<String> s2 = new Stack<>();
            List<String> list = new ArrayList<>();
            List<String> list1 = new ArrayList<>();
            int i = 0;
            while (i < centerList.size()) {
                if (centerList.get(i).matches("\\d+")) { //如果是数字
                    s2.push(centerList.get(i));
                    i++;
                } else if (centerList.get(i).equals("*") || centerList.get(i).equals("/")||centerList.get(i).equals("+")||centerList.get(i).equals("-")) { // 如果是运算符
                    if (s1.empty() || s1.peek().equals("(")) {   // 符合4.1
                        s1.push(centerList.get(i));
                        i++;
                    } else if (getLevel(centerList.get(i)) > getLevel(s1.peek())) { // 符合4.2
                        s1.push(centerList.get(i));
                        i++;
                    } else {
                        s2.push(s1.pop());
                    }
                } else {// 为括号
                    if (centerList.get(i).equals("(")) {
                        s1.push(centerList.get(i));
                        i++;
                    } else if (centerList.get(i).equals(")")) {
                        while (!s1.peek().equals("(")) {
                            s2.push(s1.pop());
                        }
                        s1.pop();
                        i++;
                    }
                }
            }
    
            //将s1剩余的运算符依次弹出并压入s2
            while (!s1.empty()){
                s2.push(s1.pop());
            }
    
            while (!s2.empty()){
                list.add(s2.pop());
            }
    
            for (int j = list.size()-1; j >= 0; j--) {
                list1.add(list.get(j));
            }
            return list1;
        }
    
        /**
         *
         * @param list
         * @return
         */
        public static int calculator(List<String> list) {
            Stack<String> stack = new Stack<>();
            for (String s : list) {
                if (s.matches("\\d+")) {//如果是数字的话,直接入栈
                    stack.push(s);
                } else { // 是符号的话,就pop出两个元素进行运算然后入栈
                    int num2 = Integer.parseInt(stack.pop());
                    int num1 = Integer.parseInt(stack.pop());
                    int res = 0;
                    if (s.equals("+")) {
                        res = num1 + num2;
                    } else if (s.equals("-")) {
                        res = num1 - num2;
                    } else if (s.equals("*")) {
                        res = num1 * num2;
                    } else if (s.equals("/")) {
                        res = num1 / num2;
                    } else {
                        throw new RuntimeException("运算符异常");
                    }
                    stack.push("" + res);
                }
            }
            return Integer.parseInt(stack.peek());
        }
    
        /**
         * 获取运算符的优先级
         *
         * @param str
         * @return 加减 0  乘除 1
         */
        public static int getLevel(String str) {
            int level = 0;
            if (str.equals("*") || str.equals("/")) {
                level = 1;
            }
            return level;
        }
    }
    
    展开全文
  • 计算机相关题目

    2019-05-07 19:43:00
    n个整数无序数组,找到每个元素后面比它大第一个数,要求时间复杂度为O(N),在面试官提醒下写出来了,用+底指针 介绍5种IO模型 异步编程事件循环 操作系统为什么要分内核态和用户态 为什么要有page ...
  • 蓝桥杯_表达式计算

    2017-04-20 09:15:00
    定义一符号和一数字怎么中缀转后缀,数据结构这本书上有。 这里简单说一下,从左往右扫描字符串,遇见数字就压入数字。 遇见符号话, 1、如果是'(',直接入栈。 2、如果是')',挨个弹出栈顶元素,...
  • 1.栈内元素个数怎么计算? 2.共享栈栈满条件? 3.顺序存储的栈top指的是?链式存储的栈top指的是?链式栈的结构是? 4.循环队列(顺序存储)中front指的是?rear指的是?链队中二者分别指的是?链队的结构是 5....
  • 使用Java求数学表达式

    千次阅读 2018-08-17 21:05:15
    但大多教程只是一Demo,该Demo只实现了位数四则运算,遇到位数以上的计算时就会出现问题。本文在此基础上进行了扩展,实现了位数以上四则运算。 整体思路: 输入表达式为中缀表达式,将该表达式转为...
  • 实现带括号四则运算器简单程序 现在不管输入什么,一回车程序就结束,什么也不输出,请问是怎么回事 ``` #include #include #define TRUE 1 #define FALSE 0 #define Stack_Size 50 ...
  • LC 224. 基本计算器

    2021-03-10 16:07:45
    题目描述 实现一基本计算器来计算简单字符串表达式 s 值。...遇到’)‘先不要让其入栈,弹出1栈顶元素放入temp保存,再弹出1栈顶元素(这个元素一定是’(’,没有为什么,按照这套
  • //用于判定运算符优先级 以决定是把运算符压栈 还是把运算符弹出来进行计算 { if(((op1=='+'||op1=='-')&&(op2=='+'||op2=='-'||op2==')'||op2=='='))||\ ((op1=='*'||op1=='/')&&(op2=='+'||op2=='-'||op...
  • 首先:计算机最喜欢一定是后缀表达式,我们只要从头到尾遍历,然后碰到数字就压入栈,碰到运算符就直接取出栈顶2个元素直接进行计算,并将结果压入栈。 那我们这里要做操作就是将中缀转成后缀。 怎么做呢? ...
  • 3.5.3 给40亿个不重复unsigned int整数,没排过序,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中? 3.5.4 在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G。 3.5.5 时分秒针...
  • 大话数据结构

    2018-12-14 16:02:18
    而只是让每个元素知道它下一个元素的位置在哪里。 3.6.1顺序存储结构不足解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表读取 ...
  • 逆波兰(后缀)表达式求值C++实现

    千次阅读 2018-04-04 10:01:08
    之前一篇文章里已经讲到里怎么将中缀表达式转化为后缀表达式:...3、如果扫描项目是一二元运算符+ - * /,则栈顶到两个元素依次出栈,计算后再将结果存入中;(接下...
  • def是一二级指针,它指向的是一一维数组的指针,数组的元素都是float. (2)double*(*gh)[10]; gh是一指针,它指向一一维数组,数组元素都是double*. (3)double(*f[10])(); f是一数组,f有10元素,元素都是...
  • 算法导论(part2)

    2010-09-09 22:54:12
    ·对动态规划元素的讨论(第15.3节)和对贪心算法元素的讨论(第16.2节)大大地扩展了。关于活动选择问题解释在贪心算法一章中开始出现,有助于读者搞清楚动态规划与贪心算法之间关系。 ·在第21.4节中,我们换...
  • 算法导论(part1)

    2010-09-09 22:51:05
    ·对动态规划元素的讨论(第15.3节)和对贪心算法元素的讨论(第16.2节)大大地扩展了。关于活动选择问题解释在贪心算法一章中开始出现,有助于读者搞清楚动态规划与贪心算法之间关系。 ·在第21.4节中,我们换...
  • Google Android SDK开发范例大全(完整版)

    热门讨论 2011-11-03 10:32:46
    但并不是每设备都需要通过一常规的计算设备来控制。想象一下传统家用电器,例如电炉、微波炉或面包机。如果您家用电器由 Android 控制,并且有一彩色触摸屏,会怎么样?如果电炉上有一 Android UI,那么...
  • java 面试题 总结

    2009-09-16 08:45:34
    堆是栈的组成元素 19、forward 和redirect的区别 forward是服务器请求资源,服务器直接访问目标地址的URL,把那个URL的响应内容读取过来,然后把这些内容再发给浏览器,浏览器根本不知道服务器发送的内容是从...
  • C++程序员面试宝典

    热门讨论 2013-04-01 13:36:19
    面试题142 如何访问的元素 162 13.4 树 162 面试题143 树的分类有哪些 162 面试题144 如何对树进行遍历 164 面试题145 如何对二叉树进行遍历 164 面试题146 如何计算二叉树的高度 166 面试题147 如何计算二叉树...
  • 如何查找容器内所有符合条件的元素 3. Python开发相关 list tuple区别 生成器和迭代器 Python类的定义和实例化方法 4. 数据结构相关 红黑树结构,查找时间复杂度 堆排序的时间复杂度 Top K排序 如何用O...
  • 新版Android开发教程.rar

    千次下载 热门讨论 2010-12-14 15:49:11
    � Android 是款开源移动计算软件平台,组建了 google 主导拥有众多产业界巨头产业联盟,有利于 高效开发、降低成本。 � 由于是源代码开放产品,对非主导厂商而言,可以避开与主导厂商在核心技术上面差距...
  • 世界500强面试题.pdf

    2019-11-01 14:33:26
    1.2.2. 下排每个数都是先前上排那十个数在下排出现次数 ..........................11 1.2.3. 设计包含 min 函数的栈 ...................................................................... 14 1.2.4. 求子...
  • C语言编程要点

    2017-09-18 00:10:37
    9.5. 通过指针或带下标的数组名都可以访问数组中的元素,哪一种方式更好呢? 141 9.6. 可以把另外一地址赋给一数组名吗? 143 9.7. array_name和&array_name有什么不同? 144 9.8. 为什么用const说明的常量不能用来...
  • 9.5 通过指针或带下标的数组名都可以访问数组中的元素,哪一种方式更好呢? 9.6 可以把另外一地址赋给一数组名吗? 9.7 array_name和&array;_name有什么不同? 9.8 为什么用const说明的常量不能用来定义...
  • 面试题142 如何访问的元素 13.4 树 面试题143 树的分类有哪些 面试题144 如何对树进行遍历 面试题145 如何对二叉树进行遍历 面试题146 如何计算二叉树的高度 面试题147 如何计算二叉树的结点 13.5 图 面试题...
  • malloc:该函数分配给定字节,并返回一指向它们指针。如果没有足够可用内存,那么它返回一空指针。 free:该函数获得指向由 malloc 分配内存片段指针,并将其释放,以便以后程序或操作系统使用...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

怎么计算栈的元素个数