LeetCode :150. 逆波兰表达式求值(含求后缀表达式和中缀转后缀表达式)

题目描述:

代码:

拓展:

中缀表达式转后缀表达式代码:

题目描述:

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

代码:

   public int evalRPN(String[] tokens){//数组长度是变化的LinkedList<Integer> stack = new LinkedList<>();//java自带的栈  容量自动变化for(String i:tokens){if(i.equals("+")){int a = stack.pop();int b = stack.pop();stack.push(a+b);}else if(i.equals("-")){int a = stack.pop();int b = stack.pop();stack.push(b-a);}else if(i.equals("*")){int a = stack.pop();int b = stack.pop();stack.push(a*b);}else if(i.equals("/")){int a = stack.pop();//a
//                System.out.println(a);int b = stack.pop();//13System.out.println(b);stack.push(b/a);}else {stack.push(Integer.parseInt(i));//转换为int类型}}return stack.pop();}

拓展:

中缀表达式转后缀表达式代码:

package 表达式;import java.util.LinkedList;public class InfixToSuffix {// 中缀表达式转后缀表达式/* a+b   ab+*  a*b-c  ab*c-*  a+b*c   abc*+* 1.遇到非字符串,直接拼串* 2.遇到运算符  判断优先级，* 如果优先级高，则直接入栈，* 否则，>= 将栈内元素出栈，拼接 再入栈* 左括号直接入栈, 右括号把遇到左括号前的所有符号都出栈* 遍历完成,栈里剩余运算符 依次出栈拼接* */public static void main(String[] args) {
//        String exp = "a+b*c";
//        String exp = "1+2*3-4/5";String exp = "1+2*3-4/5*(6+7)";System.out.println(infixToSuffix(exp));}//判断优先级  +- 1  * / 2static int priority(char c) {switch(c){case '(':return 0;case '+':case '-':return 1;case '*':case '/':return 2;default:return -1;}}// 中缀表达式转后缀表达式static String infixToSuffix(String exp){LinkedList<Character> stack = new LinkedList<>();StringBuilder sb = new StringBuilder(exp.length());for(int i=0;i<exp.length();i++){char c = exp.charAt(i);switch(c){case '+':case '-':case '*':case '/':{if(stack.isEmpty()){//栈为空，直接入栈stack.push(c);break;}else{if(priority(c)>priority(stack.peek())) {//栈顶运算符优先级低stack.push(c);break;}else{while(!stack.isEmpty()&&priority(c)<=priority(stack.peek())){//栈顶运算符优先级高或相等sb.append(stack.pop());}stack.push(c);//通过前面对比,把优先级高或相等的先拼接,之后再把优先级低的运算符入栈break;}}}case '(':stack.push(c);break;case ')':{while(!stack.isEmpty()&&stack.peek()!='('){sb.append(stack.pop());}stack.pop();//左括号弹出break;}default:{sb.append(c);break;}}}while(!stack.isEmpty()){sb.append(stack.pop());}return sb.toString();}
}