逆波兰式+栈求数学表达式｜8月更文挑战

做题之前之前我们先学习关于这个题的知识可以先往下翻大致看一下这道简简单单的小题，我的任务就是将这道题往细致的讲（因为自己菜，不细致我也不懂）

其实我的主要目的不是讲题是让大家了解波兰式和栈的结合求出数学表达式但是能 ==拿四杀何必拿三杀呢== 然后就顺便做了道面试考研必刷题 ，如果顺着这个思路的话我觉得大家完全可以拿个 ==五杀== 🙂 （即学会这道题，了解波兰式和栈，运用合理它们和==得到我==），来波团灭完成每个男人的梦想。那么弄完前戏我们开始吧。

我们先开始介绍逆波兰式：

• 逆波兰式：也叫后缀表达式（将运算符写在操作数之后）是不是有点不理解那好办来个例子：这样的表达式为中缀 a+b，ab+这样的就是后缀叫高大上点就是逆波兰式，可能这个例子有点简单来个复杂的

(a+b)*c-(a+b)/e
的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-

ps 你可能会发现这样的结果其实就是二叉树的后序遍历
复制代码

可能这个有难度对新同学，不过没关系==放心往下看==其他的我来解决这个链接里面有详解：链接视频，其实这些东西我的博文里面都有可能同学没有发现 :*

那么到底为什么计算表达式要用波兰式呢？

有这个疑问的同学说明你已经在思考了，离成功只差把文章看完了，加油！！！
解释：这种表示法的一个特点是，表达式中各个==运算是按运算符出现的顺序进行的==，故无须使用括号来指示运算顺序，因而又称为无括号式。这样是不是有点官方难懂了呢？

没关系，我来帮你，我们计算数学表达式时是不是要遵守四则混合运算规则——先乘除后加减有（）先算（）里面的。但是计算机不懂这些呀，所以聪明的人想出来==运算是按运算符出现的顺序进行的==就像 2+3*4这个中缀表达式根据四则运算我们知道先算3*4接着是2+12在计算机里我们可以先用逆波兰式转变为2 3 4 * +（方法上面已经给了）如下

问题又来了怎么实现先计算3*4呢

往下看让我们来介绍==先进后出的数据结构==——栈

再来介绍栈

• 什么是栈：来自官方的解释链接，我给出的建议就是==你可以把它想成一个数组==，就这这个数组有点特殊他只能从一端进，出而且还要==遵循先进后出的原则==。就如同如下的结构。

• 

为了减少篇幅下面有详细的构建过程代码有兴趣可以看一下，附有详细的解释，有问题可以私信。

好了懂了上面两个数据结构我们下面可以放开手干了。

必刷题

问题描述
　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
　　输入一行，包含一个后缀表达式（逆波兰式）。
输出格式
　　输出这个后缀表达式（逆波兰式）的值。
样例输入
12-345-*+（原式1-2+3*（4-5））
样例输出
-4
数据规模和约定
　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。
复制代码

这道题无论是在力扣还是ACM和蓝桥杯的练习题里面==都出现过==重要性不用我说了吧!
建栈的过程上面链接有我就不多说了，这里讲一下入栈和运算的过程：

char[] arr=equation.toCharArray();//创建字符型数组因为一会要判断+，-，*，/
		for(char i:arr) {
			int tmp=Integer.valueOf(i);//寻找数组元素的ASCLL主要是判断是数组还是运算符
			if(tmp>=48&&tmp<=57) {//如果是数字就转为整型存入栈里
				String t=String.valueOf(i);
				int int_t=Integer.valueOf(t);
				Stack.push(int_t);
			}
复制代码

判断为运算符的话以减号为例：

if(tmp==Integer.valueOf('-')) {	
					int second=Stack.pop();//先出来的是减数
					int first=Stack.pop();//接着是被减数
					int result=first-second;
					Stack.push(result);//将结果入栈
				}
复制代码

全码：

import java.util.*;
public class arithmetic {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String equation=sc.next();
		stack Stack=new stack(equation.length());

		char[] arr=equation.toCharArray();//创建字符型数组因为一会要判断+，-，*，/
		for(char i:arr) {
			int tmp=Integer.valueOf(i);//寻找数组元素的ASCLL主要是判断是数组还是运算符
			if(tmp>=48&&tmp<=57) {//如果是数字就转为整型存入栈里
				String t=String.valueOf(i);
				int int_t=Integer.valueOf(t);
				Stack.push(int_t);
			}
			else {
				if(tmp==Integer.valueOf('-')) {
					
					int second=Stack.pop();//先出来的是减数
					int first=Stack.pop();//接着是被减数
					int result=first-second;
					Stack.push(result);//将结果入栈
				}
				if(tmp==Integer.valueOf('+')) {
					int second=Stack.pop();
					int first=Stack.pop();
					int result=first+second;
					Stack.push(result);
				}
				if(tmp==Integer.valueOf('*')) {
					int second=Stack.pop();
					int first=Stack.pop();
					int result=first*second;
					Stack.push(result);
				}
				if(tmp==Integer.valueOf('/')) {
					int second=Stack.pop();
					int first=Stack.pop();
					int result=first/second;
					Stack.push(result);
				}
				
			}
		}
		System.out.println(Integer.valueOf(Stack.pop()));
		
	}
}
class stack{
	int size;  //栈大小
	int[] arrstack;//构建的栈数组
	int top=-1;//栈顶指针用来记录目前栈里面的位置
	public stack(int size) {   // 建立构造方法同时也是栈的大小输入点
		this.size=size;
		this.arrstack=new int[this.size];
	}
	public boolean Empty() { //判断栈大小是否为空
		return this.top==-1;
	}
	public boolean Full() { //判断栈是否以满
		return this.top==this.size-1;
	}
	public void push(int value) { //压栈
		if(Full()) { //压栈前先判断是否栈里面元素已满
			System.out.println("sorry stack is full");
			return ;
		}
		top++;
		arrstack[top]=value; //把刚输入的元素放到栈顶
	}
	public int pop() { //出栈
		if(Empty()) { //判断栈是否为空
			System.out.println("sorry stack is empty");
			return -1;
		}
		int ans=arrstack[top];
		//System.out.println(arrstack[top]);
		top--; //将指针下移
		return ans;
	}
	
}

复制代码