《算法通关村—计算器|逆波兰问题解析》

计算器问题

描述

LeetCode227.给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

输入：s = "3+2*2" 
输出：7

基本思路：理解题目，题目只能是加减乘除，那么加减乘除就有优先顺序，乘除先，加减后，所以在对元素进行压栈的时候乘除就直接计算了，然后把结果押入栈，最后统一进行加减，减转化为加，其实就是把数转换为负数就好。

代码

package AlgorithmForth;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 计算器问题
 *  基本思路：理解题目，题目只能是加减乘除，那么加减乘除就有优先顺序，乘除先，加减后，所以在对元素
 *           进行压栈的时候乘除就直接计算了，然后把结果押入栈，最后统一进行加减，减转化为加，
 *           其实就是把数转换为负数就好。
 *   这道题其实有个难点没放出来，如果加了括号该如何处理？？？
 */
public class CalculateSolution {
    public static int calculate(String s){
        Deque<Integer> stack = new ArrayDeque<Integer>();
        char preSign = '+'; // 默认第一个数字的前面是加号
        int num = 0;
        int n = s.length();
        for(int i = 0;i < n; ++i){
            if(Character.isDigit(s.charAt(i))){
                num = num * 10 + s.charAt(i) - '0'; // 这里的原因是有的数字可能》=10所以要做乘10处理。
            }
            if(!Character.isDigit(s.charAt(i)) && s.charAt(i)!=' '||i==n-1){
                switch (preSign){
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*' :
                        stack.push(stack.pop()*num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);
                num = 0;
            }
        }
        int ans = 0;
        while(!stack.isEmpty()){
            ans+=stack.pop();
        }
        return ans;
    }

    public static void main(String[] args) {
        String s = "5 + 100 * 3";
        System.out.println(calculate(s));
    }
}

逆波兰问题

描述

LeetCode150.根据逆波兰表示法，求表达式的值。说明：有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。也即表达式总会得出有效数值且不存在除数为 0 的情况。

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

代码

package AlgorithmForth;

import java.util.Stack;

/**
 * 逆波兰表达式
 */
public class ReversePolishNotation {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (!Character.isDigit(token.charAt(0)) && token.length() == 1) {
                /**
                 * 运算符，从栈中取出两个数进行运算
                 */
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    /**
                     * 根据运算符的种类进行计算
                     * 将结果直接入栈
                     */
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(a-b);
                        break;
                    case "*":
                        stack.push(a*b);
                        break;
                    case "/":
                        stack.push(a/b);
                        break;
                }
            }else{
                /**
                 * 整数直接入栈
                 */
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"123","456","+","123","-" };
        System.out.println(evalRPN(tokens));
    }
}