題目描述

請寫一個(gè)整數(shù)計(jì)算器，支持加減乘三種運(yùn)算和括號。

?

示例2

輸入

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

返回值

-10

?

?運(yùn)算符號有優(yōu)先級,所以使用單調(diào)棧可以解決改問題。如下代碼，效率比較低，后面優(yōu)化。

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));}/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可* 返回表達(dá)式的值* @param s string字符串 待計(jì)算的表達(dá)式* @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++) {// 判斷是否為連續(xù)的字符是不是數(shù)字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);} }

?

總結(jié)

以上是生活随笔為你收集整理的常考数据结构与算法:表达式求值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。