大话数据结构——使用栈实现简单的四则运算,数据结构四则运算

永利皇宫 ,最近在读《大话数据结构》,里面有个例子是使用栈实现四则运算,现在我用java把这个功能实现试试

代码如下:

package com.datastruct;

import java.util.ArrayList;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class StackPractice {

 private static ArrayList<String> symbolList;
 static{
  symbolList = new ArrayList<>();
  symbolList.add(SymbolEnum.ADD.getVal());
  symbolList.add(SymbolEnum.SUBTRACT.getVal());
  symbolList.add(SymbolEnum.MULTIPLY.getVal());
  symbolList.add(SymbolEnum.DIVIDE.getVal());
  symbolList.add(SymbolEnum.LEFT_BRACKET.getVal());
  symbolList.add(SymbolEnum.RIGHT_BRACKET.getVal());
 }

 public static void main(String[] args) {
  String exp = "9+(3-1)*3+10/2";
  try {
   String exp2 = convertExp(exp);
   System.out.println(cal(exp2));
  } catch (Exception e) {
   System.out.println(e.getMessage());
  }
 }

 private static boolean isNumeric(String str){ 
     Pattern pattern = Pattern.compile("[0-9]*"); 
     Matcher isNum = pattern.matcher(str);
     if( !isNum.matches() ){
         return false; 
     } 
     return true; 
  }


 /**
  * 计算后缀表达式值
  * @return
  */
 private static int cal(String exp){
  String[] expArr = exp.split(" ");
  Stack<String> calStack = new Stack<String>();
  for(int i=0;i<expArr.length;i++){
   String tmp = expArr[i];
   if(isNumeric(tmp)){//数字入栈
    calStack.push(tmp);
   }else{
    int num1 = Integer.parseInt(calStack.pop());//栈顶弹出1
    int num2 = Integer.parseInt(calStack.pop());//栈顶弹出2
    switch (tmp) {
    case "-":
     calStack.push(num2 - num1 + "");
     break;
    case "+":
     calStack.push(num2 + num1 + "");
     break;
    case "*":
     calStack.push(num2 * num1 + "");
     break;
    case "/":
     calStack.push(num2 / num1 + "");
     break;
    default:
     break;
    }
   }
  }
  return Integer.parseInt(calStack.pop());
 }

 /**
  * 中缀表达式转为后缀表达式
  * @return
  */
 private static String convertExp(String exp) throws Exception{
  //字符串转数组
  char[] expArr = exp.toCharArray();
  StringBuffer sb = new StringBuffer();
  Stack<String> symbolStack = new Stack<>();
  boolean isLastCharNumberFlag = true;
  for(int i = 0;i<expArr.length;i++){
   char curChar = expArr[i];
   //若为数字添加 若为符号则放入栈计算
   if(Character.isDigit(curChar)){
    if(isLastCharNumberFlag){
     sb.append(curChar);
    }else{
     sb.append(" ").append(curChar);
    }

    isLastCharNumberFlag = true;
   }else if(symbolList.contains(String.valueOf(curChar))){//符号
    //
    String symbol = String.valueOf(curChar);
    if(SymbolEnum.RIGHT_BRACKET.getVal().equals(symbol) 
      )
    {

     //如果是右括号,得匹配左括号 
     String symbolStr = symbolStack.pop();
     while(!SymbolEnum.LEFT_BRACKET.getVal().equals(symbolStr)){
      sb.append(" ").append(symbolStr);
      symbolStr = symbolStack.pop();
     }
     isLastCharNumberFlag = false;
     continue;
    }else if(SymbolEnum.DIVIDE.getVal().equals(symbol) ||
      SymbolEnum.MULTIPLY.getVal().equals(symbol) ){
    }else{
     if(symbolStack.isEmpty()){
      symbolStack.push(symbol);
      continue;
     }
     String symbolStr = symbolStack.peek();
     if(SymbolEnum.DIVIDE.getVal().equals(symbolStr) ||
       SymbolEnum.MULTIPLY.getVal().equals(symbolStr)){
      while(!symbolStack.isEmpty()){
       sb.append(" ").append(symbolStack.pop());
      }
      symbolStack.push(symbol);
      isLastCharNumberFlag = false;
      continue;
     }
    }
    symbolStack.push(symbol);
    isLastCharNumberFlag = false;
   }
  }
  while(!symbolStack.isEmpty()){
   sb.append(" ").append(symbolStack.pop());
  }
  return sb.toString();
 }


 /**
  * 运算符枚举
  * @author Administrator
  *
  */
 enum SymbolEnum{
  ADD("+"), SUBTRACT("-"),MULTIPLY("*"),DIVIDE("/"),LEFT_BRACKET("("),RIGHT_BRACKET(")");
  private String val;

  public String getVal(){
   return val;
  }

  private SymbolEnum(String val){
   this.val = val;
  }
 }
}

  程序暂时有些bug,如表达式合法性没有校验,不能输入多个括号等

最近在读《大话数据结构》,里面有个例子是使用栈实现四则运算,现在…

最近在读《大话数据结构》,里面有个例子是使用栈实现四则运算,现在我用java把这个功能实现试试

代码如下:

网站地图xml地图