使用多堆棧評估前綴表達式

Question

我需要幫助將字符串推入堆棧。

對於我的任務，我將評估前綴表達式，並且我們需要使用堆棧跟蹤子表​​達式，因爲它們是被評估的以及尚未被評估的操作數。

我遇到的主要問題是將「+」和「*」推到Stack<String>。我嘗試了多種方法，但都沒有成功。

請參閱示例I/O和代碼。我已經通過相關方法發表了評論。代碼頂部附近的第一個評論是我自己的筆記，因爲我會不時離開計算機。

樣品I/O：

{Please enter a prefix expression: + 2 51 
Popping Integers Stack: 
2 
51 
Popping Operators Stack: 
*nothing shows here* 

代碼

import java.io.*; 
import java.util.*; 

public class test211 
{ 
    /* create two stacks, one for operators and one for integers 
    * accept user input as a string with space as delimiter use a tokenizer 
    * use If statement to determine if token is integer or 
    * operator and pop each integer/operator into a variable 
    * use operator pop and If statement to determine order of operations 
    * possible use of counters to help determine order of operations 
    * 
    * 
    * set input to arraylist then tokenize to seperate into 2 stacks 
    */ 

    public static void main(String [] args) throws IOException 
    { 
     tokenizer(); 
    } 


    /*This method is supposed to take the user input and separate it into 
    * tokens. Once separated, I am currently sending the tokens through 2 different methods 
    * to establish my operand stacks and operator stacks 
    */ 

    private static void tokenizer() 
    { 
     Stack<String> operators = new Stack<String>(); 
     Stack<Integer> integers = new Stack<Integer>(); 
     Stack<String> expression = new Stack<String>(); 
     ArrayList<String> tokens = new ArrayList<String>(); 
     String user = userInput(); 
     tokens = tokeniseInput(user); 

     /*The next three methods convert my input string into a Stack<String> 
     * and pass that Stack<String> to two methods to separate the 
     * operators and operands 
     */ 

     expression = buildStack(tokens); 
     integers = operatorSeparator(expression); 
     operators = operandSeparator(expression); 
     System.out.println("Popping Integers Stack:"); 
     for (Integer i : integers) 
     { 
      System.out.println(i + " "); 
     } 
     System.out.println("Popping Operators Stack:"); 
     for (String s : operators) 
     { 
      System.out.println(s + " "); 
     } 

    } 



    private static void evaluator(Stack<String> operators, Stack<Integer> integers) 
    { 

     int result; 
     if(operators.empty()) 
     { 
      result = integers.pop(); 
      System.out.println("Result: " + result + " only printed if operator stack was empty."); 
     } 

     else if (operators.peek() == "+") 
     { 
      int x = integers.pop(); 
      int y = integers.pop(); 
      result = x + y; 
      System.out.println("Result: " + result + " only printed if operator stack next was +."); 
     } 

     else if (operators.peek() == "*") 
     { 
      if (operators.empty()) 
      { 
       result = integers.pop() * integers.pop(); 
       System.out.println("Result: " + result + " only printed if operator stack next was * and then stack empty"); 
      } 
     } 
    } 


    private static String userInput() 
    { 
     String input;  
     Scanner keyboard = new Scanner(System.in);  
     System.out.print("Please enter a prefix expression: "); 
     input = keyboard.nextLine(); 
     keyboard.close(); 
     return input; 
    } 


    public static ArrayList<String> tokeniseInput(String u) 
    { 
     ArrayList<String> arrString = new ArrayList<String>(); 
     StringTokenizer str = new StringTokenizer(u); 
     while(str.hasMoreTokens()) 
      { 
       String s = str.nextToken(); 
       arrString.add(s); 
      } 

     return arrString; 
    } 

    public static Stack<Integer> buildIntStack(ArrayList<String> arrString) 
    { 
     Stack<Integer> stack = new Stack<Integer>(); 
     for(int i=arrString.size()-1; i>=0;i--) 
     { 
      if (!arrString.equals("+") || !arrString.equals("*")) 
      { 
       int temp = Integer.parseInt(arrString.get(i)); 
       stack.push(temp); 
      } 

     } 
     return stack; 
    } 


    public static Stack<String> buildStrStack(ArrayList<String> arrString) 
    { 
     Stack<String> stack = new Stack<String>(); 
     for(int i=arrString.size()-1; i>=0;i--) 
     { 
      if (arrString.equals("+") || arrString.equals("*")) 
      { 
       stack.push(arrString.get(i)); 
      } 
     } 
     return stack; 
    } 


    /*Method to take input string and convert to Stack<String> 
    */ 
    public static Stack<String> buildStack(ArrayList<String> arrString) 
    { 
     Stack<String> stack = new Stack<String>(); 
     for(int i=arrString.size()-1; i>=0;i--) 
     { 
      stack.push(arrString.get(i)); 
     } 
     return stack; 
    } 

    /*Method to separate operational symbols from integers 
    */ 
    public static Stack<String> operandSeparator(Stack<String> stack) 
    { 
     Stack<String> temp = new Stack<String>(); 
     while (!stack.empty()) 
     { 
      String popped = stack.pop(); 
      if(popped.compareTo("+") == 0) 
      { 
       temp.push("+"); 
      } 
      else if(popped.compareTo("*") == 0) 
      { 
       temp.push("*"); 
      } 
     } 
     return temp; 
    } 

    /*Method to separate integers from operational symbols 
    */ 
    public static Stack<Integer> operatorSeparator(Stack<String> stack) 
    { 
     Stack<Integer> temp = new Stack<Integer>(); 
     while (!stack.empty()) 
     { 
      String popped = stack.pop();    
      if(!(popped.compareTo("+") == 0 || popped.compareTo("*")==0)) 
      { 
       int x = Integer.parseInt(popped); 
       temp.push(x); 
      } 
     } 
     return temp; 
    } 
} 

Answer 1

行整數= operatorSeparator（表達）後;表達式堆棧是空的。另外，你確定你需要使用那麼多堆棧並將數據從堆棧移動到堆棧嗎？

爲什麼不使用更簡單的方法。這例如。

import java.util.ArrayList; 
import java.util.List; 
import java.util.Stack; 

class Prefix { 
    static List<Object> tokenize(String input) { 
    ArrayList<Object> tokens = new ArrayList<>(); 
    for(String s: input.split("\\s+")) { 
     try { 
     double d = Double.parseDouble(s); 
     tokens.add(d); 
     } catch(NumberFormatException e) { 
     tokens.add(s); 
     } 
    } 
    return tokens; 
    } 

    static double eval(List<Object> expr) { 
    Stack<Double> stack = new Stack<>(); 
    for(int i = expr.size() - 1; i >= 0; i--) { 
     Object o = expr.get(i); 
     if(o instanceof Double) { 
     stack.push((Double)o); 
     } else if(o.equals("+")) { 
     stack.push(stack.pop() + stack.pop()); 
     } else if(o.equals("*")) { 
     stack.push(stack.pop() * stack.pop()); 
     } 
    } 
    return stack.pop(); 
    } 

    public static void main(String[] args) { 
    List<Object> tokens = tokenize("* + 3.2 4.7 + 5 6"); 
    System.out.println(tokens); 
    System.out.println(eval(tokens)); 
    } 
}