中缀表达式转换成后缀表达式及后缀表达式的运算
import java.util.Stack;import java.util.regex.Matcher;import java.util.regex.Pattern;/** * 四则运算 + - * / () * 1、由中缀到后缀 * 2、由后缀算结果 * User: yfzhangbin * Date: 13-12-26 * Time: 上午11:58 */public class Operation { private static Stack<Character> symbolStack = new Stack<Character>(); private static Stack<Integer> numStack = new Stack<Integer>(); private static Pattern numberPattern = Pattern.compile("\\d*"); // 匹配数字 public static void main(String[] args) { String express = "425-32*2+(8-5*7)*9+1"; // "9+(3-1)*3+10/2"; express = infixToPostfix(express); System.out.println(express); System.out.println(calculate(express)); } /** * 中缀表达式转换成后缀表达式 * @param express 中缀表达式 * @return 后缀表达式 */ private static String infixToPostfix(String express) { boolean isSymbol = false; StringBuilder result = new StringBuilder(); for (int i = 0; i < express.length(); i ++) { char c = express.charAt(i); if (' ' == c) continue; Matcher matcher = numberPattern.matcher(Character.toString(c)); if (matcher.matches()) { if (isSymbol) { // 用来分割数字和算数运算符，用空格隔开 result.append(" "); isSymbol = false; } result.append(c); } else { isSymbol = true; if (symbolStack.size() == 0) { symbolStack.push(c); // 插入第一个符号元素 continue; } if (')' == c) { // 栈顶元素若为')',则依次弹栈直到最近的'('被弹出 char top = symbolStack.pop(); while (top != '(' && symbolStack.size() > 0) { result.append(" ").append(top); top = symbolStack.pop(); } } else if ('+' == c || '-' == c) { // 插入元素若为低优先级的'+','-'时，则先弹出栈顶元素再入栈; 如果当前栈顶元素为'('时，直接入栈 char top = symbolStack.peek(); while (top != '(' && symbolStack.size() > 0) { result.append(" ").append(symbolStack.pop()); if (symbolStack.size() > 0) top = symbolStack.peek(); } symbolStack.push(c); } else { // 字符为(,*,/时直接入栈 symbolStack.push(c); } } } while (symbolStack.size() > 0) { result.append(" ").append(symbolStack.pop()); } return result.toString(); } /** * 后缀表达式的运算 * @param express 后缀表达式 * @return 运算结果 */ private static int calculate(String express) { String[] parts = express.split(" "); for (String part : parts) { Matcher matcher = numberPattern.matcher(part); if (matcher.matches()) { numStack.push(Integer.parseInt(part)); } else if (numStack.size() >= 2) { int n2 = numStack.pop(); int n1 = numStack.pop(); //System.out.println(n1 + part +n2); // 打印运算过程 if ("*".equals(part)) { numStack.push(n1 * n2); } else if ("/".equals(part)) { numStack.push(n1 / n2); } else if ("+".equals(part)) { numStack.push(n1 + n2); } else if ("-".equals(part)) { numStack.push(n1 - n2); } } } return numStack.pop(); }}
?
