常考数据结构与算法:表达式求值

题目描述

请写一个整数计算器，支持加减乘三种运算和括号。

 

示例2

输入

"(2*(3-4))*5"

返回值

-10

 

 运算符号有优先级,所以使用单调栈可以解决改问题。如下代码，效率比较低，后面优化。

import java.util.Stack;public class AlgoSolveMe {public static void main(String[] args) {String s = "(2*(3-4))*5";//s="100+100";//s = "((10+2)*10-(100-(10+20*10-(2*3)))*10*1*2)-2"; // 2198AlgoSolveMe algoSolveMe = new AlgoSolveMe();System.out.println(algoSolveMe.solve(s));}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 返回表达式的值* @param s string字符串 待计算的表达式* @return int整型*/public int solve (String s) {// "(2*(3-4))*5"Stack<Integer> opValue = new Stack<>();Stack<Character> opSign = new Stack<>();/*((10+2)*10-(100-(10+20*10-(2*3)))*10*1*2)-2(120-(100-(10+20*10-6))*10*1*2)-2(120-(100-204)*10*1*2)-2(120-(-104)*10*1*2)-2(120-(-2080))-22200-2 = 2198*/String temp = "";for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(ch == '('){opSign.push(ch);}else if((ch == '*'|| ch == '/' || ch == '+'|| ch == '-') ) {if(opSign.isEmpty() || opSign.peek()=='(') {opSign.push(ch);}else if(ch == '+' || ch == '-'){while(!opSign.isEmpty() && opSign.peek() != '(') {doOper(opValue, opSign);}opSign.push(ch);}else if((ch == '*' || ch == '/') && (opSign.peek()=='+' || opSign.peek()=='-') ){opSign.push(ch);}else if(ch == '*' || ch == '/'){while(!opSign.isEmpty() && opSign.peek() != '(' && opSign.peek()!='+' && opSign.peek()!='-') {doOper(opValue, opSign);}opSign.push(ch);}}else if(ch == ')') {while(opSign.peek() != '(') {doOper(opValue, opSign);}// 弹出右边括号opSign.pop();}else{temp += ch;for (int j = i+1; j < s.length(); j++) {// 判断是否为连续的字符是不是数字if(s.charAt(j)<48 || s.charAt(j)>57) {break;}i++;temp += s.charAt(j);}opValue.push(Integer.valueOf(temp));temp= "";}}while(!opSign.isEmpty()){doOper(opValue, opSign);}return opValue.peek();}private void doOper(Stack<Integer> opValue,Stack<Character> opSign){int op1=0,op2=0;op2 = opValue.pop();op1 = opValue.pop();char ops = opSign.pop();int res = 0;if (ops == '-') {res = op1 - op2;} else if (ops == '+') {res = op1 + op2;} else if (ops == '*') {res = op1 * op2;} else if (ops == '/') {res = op1 / op2;}opValue.push(res);} }

 

总结

以上是生活随笔为你收集整理的常考数据结构与算法:表达式求值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。