四则运算 一、题目 二、总体思路 三、分割算术表达式 四、将中缀转换成后缀表达式 五、对后缀表达式进行求值 六、实现和测试
输入一个字符串格式的算术表达式，对其进行求值。
字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。
算术表达式的有效性由调用者保证。
接口如下：
/* 功能：四则运算 * 输入：strExpression：字符串格式的算术表达式，如: "3+2*{1+2*[-4/(8-6)+7]}" * 返回：算术表达式的计算结果 */ public static int calculate(String strExpression) { /* 请实现*/ return 0; }
二、总体思路
1、先对字符串格式的算术表达式进行分割，将操作数、操作符和括号分割开来，并存储在ArrayList中。
2、对上述分割开来的算术表达式ArrayList进行转换，转换成后缀表达式。
3、对后缀表达式进行求值。
三、分割算术表达式
//'-' may be minus operator or negative sign private static boolean isDigital(char c, String infixExpression, int i) { //don't need to think about exception //may be a part of digital if(c == '-') { if(i == 0) return true;//For example: -14*24, a part of digital(-14) char prev = infixExpression.charAt(i-1); if('0' <= prev && prev <= '9') return false;//For example: 34-56, not a part of digital else if(prev == ')') return false;//For example: 3-10+(0+(10+5+3)-10), not a part of digital else return true;//For example: 45*12/-12, a part of digital(-12); (-45/12)+2, a part of digital(-45) } return '0' <= c && c <= '9'; }
private static ArrayList<String> splitExpression(String infixExpression) { ArrayList<String> infix = new ArrayList<String>(); infixExpression = infixExpression.replace('{', '('); infixExpression = infixExpression.replace('}', ')'); infixExpression = infixExpression.replace('[', '('); infixExpression = infixExpression.replace(']', ')'); StringBuilder operand = new StringBuilder(); for(int i = 0; i < infixExpression.length(); i++) { char c = infixExpression.charAt(i); if(!isDigital(c, infixExpression, i)) { if(operand.length() != 0) { infix.add(operand.toString());//last operand operand = new StringBuilder();//empty } infix.add(c + "");//operator } else { operand.append(c); if(i == infixExpression.length() - 1){ infix.add(operand.toString());//the last operand in the end } } } return infix; }
这里需要重点处理‘-’这个符号，有可能为减号或者为负号。
思路如下：
1、首先将[]{}等括号替换成()，方便统一处理。
2、遍历字符串表达式，如果当前字符为数字，那么先缓存到操作数operand字符串中。如果是最后一个字符，将operand添加到输出中。
3、如果当前字符为非数字，那么先添加operand到输出中（非空），再将当前操作符添加到输出中。
判断是否为数字的思路（需要特别处理‘-’符号）：
1、当前符号为‘-’时：
如果前一个字符是‘0’到‘9’时，其为非数字。
如果前一个字符是‘)’时，其为非数字。
如果前一个字符时‘*’或‘/’或‘+’或‘-’或‘(’时，其为数字的一部分。
2、当前符号不为‘-’时：
只需判断是否为‘0’到‘9’，若是则为数字，若不是，则为非数字。
四、将中缀转换成后缀表达式
private static boolean isOperand(String item) { //don't need to handle the situation when item is null if(item.length() > 1) { return true;//must be operand } else {//don't need to think about the situation that length lower than 1 if('0' <= item.charAt(0) && item.charAt(0) <= '9') { return true; } else { return false; } } }
//A < B? private static boolean isALowerB(String operatorA, String operatorB) { if(operatorB.equals("(")) {//highest priority return true;//dont need to handle the situation that operatorA is "(" } else if(operatorB.equals("*") || operatorB.equals("/")) { if(operatorA.equals("+") || operatorA.equals("-")) { return true;//A is lower } else { return false;//the same } } else { return false;//operatorB is already lowest } }
private static ArrayList<String> convertInfix2Postfix(ArrayList<String> infix) { ArrayList<String> postfix = new ArrayList<String>(); Stack<String> st = new Stack<String>(); while(!infix.isEmpty()) { String s = infix.remove(0); if(isOperand(s)) { postfix.add(s);//operand, placed immediately } else { if(s.equals(")")) {//right parenthesis, pop the stack until encounter a (correspoding) left parenthesis while(!st.empty() && !st.peek().equals("(")) {//don't need to think about the exception postfix.add(st.pop()); } st.pop();//pop left parenthesis, discard it. } else { //pop until find an entry of lower priority while(!st.isEmpty() ) { if(isALowerB(st.peek(), s)) { break; } else { if(st.peek().equals("(")) break;//never remove a '(' from the stack except when processing a ')' postfix.add(st.pop()); } } st.push(s);//push new entry } } }
while(!st.empty()) { postfix.add(st.pop()); }
return postfix; }
思路：
1、如果当前字符串是操作数，直接将这个操作数添加到输出中。
2、如果当前字符串是操作符，那么需要进一步处理。需要用一个stack来缓存。
3、如果当前操作符是“)”，那么需要将stack中所有操作符依次添加到输出中直到遇到相匹配的“(”。“(”直接丢弃。
4、剩余的情况，需要先将stack中的操作符添加到输出，直到遇到更低优先级的操作符（“(”例外，不输出，除非遇到相匹配的“)”）或者栈为空。
5、再将新的操作符添加到stack中。
6、处理完所有字符串之后，需要将stack中剩余的所有操作符依次添加到输出中。
五、对后缀表达式进行求值
private static int calculatePostfix(ArrayList<String> postfix) { Stack<Integer> st = new Stack<Integer>(); while(!postfix.isEmpty()) { String s = postfix.remove(0); if(isOperand(s)) { st.push(Integer.parseInt(s)); } else { char operator = s.charAt(0); int temp = 0; switch (operator) { case '+': st.push(st.pop() + st.pop()); break; case '-': temp = st.pop(); st.push(st.pop() - temp); break; case '*': st.push(st.pop() * st.pop()); break; case '/': temp = st.pop(); st.push(st.pop() / temp); break; default: break; } } } return st.pop(); }
思路：
1、如果是操作数，压栈。
2、如果是操作符，弹出两个操作数，进行相应的计算，再将结果压栈。
重复上述操作，直到处理完表达式，此时栈中应该刚好剩余一个操作数，即为最终结果。
六、实现和测试
package com.qiusongde; import java.util.*; public class Test { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { String input = sc.next(); System.out.println(calculate(input)); } sc.close(); } public static int calculate(String infixExpression) { ArrayList<String> list = new ArrayList<>(); list = splitExpression(infixExpression); list = convertInfix2Postfix(list); int result = calculatePostfix(list); return result; } //'-' may be minus operator or negative sign private static boolean isDigital(char c, String infixExpression, int i) { //don't need to think about exception //may be a part of digital if(c == '-') { if(i == 0) return true;//For example: -14*24, a part of digital(-14) char prev = infixExpression.charAt(i-1); if('0' <= prev && prev <= '9') return false;//For example: 34-56, not a part of digital else if(prev == ')') return false;//For example: 3-10+(0+(10+5+3)-10), not a part of digital else return true;//For example: 45*12/-12, a part of digital(-12); (-45/12)+2, a part of digital(-45) } return '0' <= c && c <= '9'; } private static ArrayList<String> splitExpression(String infixExpression) { ArrayList<String> infix = new ArrayList<String>(); infixExpression = infixExpression.replace('{', '('); infixExpression = infixExpression.replace('}', ')'); infixExpression = infixExpression.replace('[', '('); infixExpression = infixExpression.replace(']', ')'); StringBuilder operand = new StringBuilder(); for(int i = 0; i < infixExpression.length(); i++) { char c = infixExpression.charAt(i); if(!isDigital(c, infixExpression, i)) { if(operand.length() != 0) { infix.add(operand.toString());//last operand operand = new StringBuilder();//empty } infix.add(c + "");//operator } else { operand.append(c); if(i == infixExpression.length() - 1){ infix.add(operand.toString());//the last operand in the end } } } return infix; } private static boolean isOperand(String item) { //don't need to handle the situation when item is null if(item.length() > 1) { return true;//must be operand } else {//don't need to think about the situation that length lower than 1 if('0' <= item.charAt(0) && item.charAt(0) <= '9') { return true; } else { return false; } } } //A < B? private static boolean isALowerB(String operatorA, String operatorB) { if(operatorB.equals("(")) {//highest priority return true;//dont need to handle the situation that operatorA is "(" } else if(operatorB.equals("*") || operatorB.equals("/")) { if(operatorA.equals("+") || operatorA.equals("-")) { return true;//A is lower } else { return false;//the same } } else { return false;//operatorB is already lowest } } private static ArrayList<String> convertInfix2Postfix(ArrayList<String> infix) { ArrayList<String> postfix = new ArrayList<String>(); Stack<String> st = new Stack<String>(); while(!infix.isEmpty()) { String s = infix.remove(0); if(isOperand(s)) { postfix.add(s);//operand, placed immediately } else { if(s.equals(")")) {//right parenthesis, pop the stack until encounter a (correspoding) left parenthesis while(!st.empty() && !st.peek().equals("(")) {//don't need to think about the exception postfix.add(st.pop()); } st.pop();//pop left parenthesis, discard it. } else { //pop until find an entry of lower priority while(!st.isEmpty() ) { if(isALowerB(st.peek(), s)) { break; } else { if(st.peek().equals("(")) break;//never remove a '(' from the stack except when processing a ')' postfix.add(st.pop()); } } st.push(s);//push new entry } } } while(!st.empty()) { postfix.add(st.pop()); } return postfix; } private static int calculatePostfix(ArrayList<String> postfix) { Stack<Integer> st = new Stack<Integer>(); while(!postfix.isEmpty()) { String s = postfix.remove(0); if(isOperand(s)) { st.push(Integer.parseInt(s)); } else { char operator = s.charAt(0); int temp = 0; switch (operator) { case '+': st.push(st.pop() + st.pop()); break; case '-': temp = st.pop(); st.push(st.pop() - temp); break; case '*': st.push(st.pop() * st.pop()); break; case '/': temp = st.pop(); st.push(st.pop() / temp); break; default: break; } } } return st.pop(); } }
测试数据：
3-10+(0+(10+5+3)-10)
输出结果：
1