前言
2023-9-24 23:02:07
以下内容源自《【学习算法】》
仅供学习交流使用
推荐
无
计算表达式
逆波兰表达式求值
class Solution { public int evalRPN(String[] tokens) { Stack<String> stack=new Stack(); for(String s:tokens){ if(s.equals("+")){ int b=Integer.parseInt(stack.pop()); int a=Integer.parseInt(stack.pop()); int c=a+b; stack.push(Integer.toString(c)); }else if(s.equals("-")){ int b=Integer.parseInt(stack.pop()); int a=Integer.parseInt(stack.pop()); int c=a-b; stack.push(Integer.toString(c)); }else if(s.equals("*")){ int b=Integer.parseInt(stack.pop()); int a=Integer.parseInt(stack.pop()); int c=a*b; stack.push(Integer.toString(c)); }else if(s.equals("/")){ int b=Integer.parseInt(stack.pop()); int a=Integer.parseInt(stack.pop()); int c=a/b; stack.push(Integer.toString(c)); }else{ stack.push(s); } } return Integer.parseInt(stack.pop()); } }
中缀表达式求值
LeetCode
class Solution { public 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'; } 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; } }
算法优先分析法
import java.util.ArrayDeque; import java.util.Deque; import java.util.HashMap; import java.util.HashSet; public class Solution { public static void main(String[] args) { String token="3/2"; int res=calculate(token); System.out.println(res); } static HashSet<Character> opSet =new HashSet<>(); static { opSet.add('#'); opSet.add('+'); opSet.add('-'); opSet.add('*'); opSet.add('/'); opSet.add('('); opSet.add(')'); } static HashMap<Character,HashMap<Character,Character>> relation=new HashMap<>(); static { HashMap<Character,Character> map=new HashMap<>(); map.put('+','>'); map.put('-','>'); map.put('*','<'); map.put('/','<'); map.put('(','<'); map.put(')','>'); map.put('#','>'); relation.put('+',map); relation.put('-',map); map=new HashMap<>(); map.put('+','>'); map.put('-','>'); map.put('*','>'); map.put('/','>'); map.put('(','<'); map.put(')','>'); map.put('#','>'); relation.put('*',map); relation.put('/',map); map=new HashMap<>(); map.put('+','<'); map.put('-','<'); map.put('*','<'); map.put('/','<'); map.put('(','<'); map.put(')','='); relation.put('(',map); map=new HashMap<>(); map.put('+','>'); map.put('-','>'); map.put('*','>'); map.put('/','>'); map.put(')','>'); map.put('#','>'); relation.put(')',map); map=new HashMap<>(); map.put('+','<'); map.put('-','<'); map.put('*','<'); map.put('/','<'); map.put('(','<'); map.put('#','='); relation.put('#',map); } public static int calculate(String s) { s = s.replaceAll("\\s+",""); s += '#'; Deque<Integer> numStack = new ArrayDeque<>(); Deque<Character> opStack = new ArrayDeque<>(); opStack.push('#'); int i = 0; char ch = s.charAt(i); while (ch != '#' || opStack.peek() != '#') { if (!opSet.contains(ch)) { while (ch == ' ') { ch = s.charAt(++i); } int data = 0; data = ch - '0'; ch = s.charAt(++i); while (!opSet.contains(ch)) { data = data * 10 + ch - '0'; ch = s.charAt(++i); } numStack.push(data); } else { switch (compare(opStack.peek(), ch)) { case '<': opStack.push(ch); ch = s.charAt(++i); break; case '=': char x = opStack.pop(); ch = s.charAt(++i); break; case '>': char op = opStack.pop(); Integer data2 = numStack.pop(); Integer data1 = numStack.pop(); int val = cal(data1, op, data2); numStack.push(val); break; } } } int val = numStack.pop(); return val; } private static int cal(Integer data1, char op, Integer data2) { switch (op){ case '+': return data1+data2; case '-': return data1-data2; case '*': return data1*data2; case '/': return data1/data2; default: return 0; } } private static char compare(char op1, char op2) { return relation.get(op1).get(op2); } }
最后
我们都有光明的未来
祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦
