자바 데이터 구조 - 중간 순서 표현 식 전환 후속 표현 식 구현

7814 단어 데이터 구조
자바 가 이 를 실현 하 는 방법 을 찾 으 려 고 했 는데 어젯밤 에 한참 을 찾 았 지만 자바 가 실현 하 는 소스 코드 를 찾 지 못 했 습 니 다. (정상 적 이 고 알 아 볼 수 있 습 니 다)
응, 이 건 내 가 과학 인터넷 이 없다 고 탓 할 수 밖 에 없어.
그래서 자기가 쓰 고 싶 어 요.
비극
오전 8 시 부터 이 시간 까지 bug 수많은 오류 가 있 었 습 니 다.
나 지금 기분 나 빠.
창고 로 이 루어 진 거 예요.
테스트 용례:
입력: 1 + 2 * 3 + (4 * 5 + 6) * 7 = 
출력: 1 2 3 * + 4 5 * 6 + 7 * +
중 서 를 후 서 로 바꾸다
package    _     ;

import java.util.Scanner;

/**
 *     :        (    +-*   ) a + b * c + ( d * e + f ) * g          
 * 
 * @author nangua
 */
public class Stack_test {
	private static Scanner sc;
	//        
	private static Operator topOperator = new Operator();

	public static void main(String[] args) {
		System.out.println("      (     ,  1 + 2 * ( 1 + 2 ) ):");
		sc = new Scanner(System.in);
		String input = sc.nextLine();
		//         
		Scalculation1(input);
	}

	/**
	 *              
	 * 
	 * @param input
	 */
	private static void Scalculation1(String input) {
		//                
		String[] expression = input.split(" ");

		@SuppressWarnings("rawtypes")
		MyStack> outputStack = new MyStack(); //    

		@SuppressWarnings("rawtypes")
		MyStack> operatorStack = new MyStack(); //     

		//   (   
		int leftBracketsPosition = -1;
		//         (       0,1,2...)
		int osCount = -1;
		//            

		System.out.println("        " + expression.length);

		//        
		for (int i = 0; i < expression.length; i++) {

			//           
			//      
			try {
				Integer t = Integer.valueOf(expression[i]);
				outputStack.push(t); //            

				//       
			} catch (Exception e) {

				//       Operator
				Operator storageOperator = new Operator();
				//                        
				switch (expression[i]) {
				case "*":
					storageOperator.setValue("*");
					break;
				case "/":
					storageOperator.setValue("/");
					break;
				case "+":
					storageOperator.setValue("+");
					break;
				case "-":
					storageOperator.setValue("-");
					break;
				case "(":
					storageOperator.setValue("(");
					//   (   
					break;
				case ")":
					storageOperator.setValue(")");
					break;
				case "=":
					storageOperator.setValue("=");
				}

				//           
				if (osCount != -1) {
					if (storageOperator.value.endsWith("=")) {
						while (osCount != -1) {
							outputStack.push(operatorStack.pop());
							osCount--;
						}
					} else if (storageOperator.value.endsWith("(")) {
						//       
						operatorStack.push(storageOperator);
						osCount++;
						leftBracketsPosition = osCount;
						topOperator = (Operator) operatorStack.top();

					} else if (storageOperator.value.endsWith(")")) {
						System.out.println("qqqqqqqqqqqqq: " + osCount);
						while ((osCount != leftBracketsPosition) && (osCount >= 1)) {
							outputStack.push(operatorStack.pop());
							osCount--;
						}
						//   (    
						operatorStack.pop();
						osCount--;
						if (osCount != -1) {
							topOperator = (Operator) operatorStack.top();
						}

					} else if ((topOperator.priority >= storageOperator.priority)) {


						while (((topOperator.priority >= storageOperator.priority))) {

							if (topOperator.value.equals("(")) {
								//       
								operatorStack.push(storageOperator);
								osCount++;
								topOperator = (Operator) operatorStack.top();
								break;
							} else {
								if (osCount == -1) { //         
									//       
									operatorStack.push(storageOperator);
									osCount++;
									topOperator = (Operator) operatorStack.top();
									break;
								} else {
									//           
									outputStack.push(topOperator);
									//  operator                    
									operatorStack.pop();
									osCount--;
									if (osCount!=-1) {
										topOperator = (Operator) operatorStack.top();
									} else {
										//       
										operatorStack.push(storageOperator);
										osCount++;
										topOperator = (Operator) operatorStack.top();
										break;
									}
								}
							}
						}
					 

					} else if ((topOperator.priority <= storageOperator.priority)) {
						//       
						operatorStack.push(storageOperator);
						osCount++;
						topOperator = (Operator) operatorStack.top();

					}
				} else {
					//          
					operatorStack.push(storageOperator);
					osCount++;
					topOperator = (Operator) operatorStack.top();

				}

			}
		}

		System.out.println("******************  *********************");
		System.out.println("          :");
		outputStack.show();
		System.out.println();
		System.out.println("     :" + outputStack.count);

	}

	/**
	 *         
	 * 
	 * @author nangua
	 */
	static class MyStack {
		MyStack() {
		}

		Object[] array = new Object[1];;
		//       
		int count = 0;
		//     
		Object topOfStack = "-1";

		private void show() {
			Object o = new Object();
			for (int i = 0; i < array.length; i++) {
				o = array[i];
				if (o instanceof Operator) {
					Operator ceshi = (Operator) o;
					if ((!ceshi.value.equals("(")) && (!ceshi.value.equals(")"))) {
						System.out.print(" " + ceshi.value);
					}

				} else {
					System.out.print(" " + o);
				}
			}
		}

		/**
		 * push  
		 * 
		 * @param num
		 */
		private void push(Object num) {
			//       
			if (count == 0) {
				array[count] = num;
			} else {
				//        ,    
				Object[] newarray = new Object[count + 1];
				//     
				for (int i = 0; i < array.length; i++) {
					newarray[i] = array[i];
				}
				array = newarray;
				array[count] = num;
			}
			count++;
			topOfStack = num;
		}

		/**
		 *           
		 */
		private Object next() {
			//           2 
			if (count - 1 >= 0) {
				return array[count - 1];
			}
			return "    next";
		}

		/**
		 *   
		 * 
		 * @return
		 */
		private Object pop() {
			//       
			if (count == 0) {
				try {
					throw new Exception("      pop");
				} catch (Exception e) {
					e.printStackTrace();
				}
				return "    pop";
			} else {
				if (count == 1) {
					topOfStack = array[0];
					count = 0;
				} else {
					topOfStack = array[count - 1];
					//     
					Object[] newarray = new Object[count - 1];
					for (int j = 0; j < newarray.length; j++) {
						newarray[j] = array[j];
					}
					array = newarray;
					count--;
				}
				return topOfStack;
			}
		}

		/**
		 *       
		 */
		private Object top() {
			//       
			if (count == 0) {
				try {
					throw new Exception("      top");
				} catch (Exception e) {
					e.printStackTrace();
				}
				return "    top";
			} else {
				if (count == 1) {
					topOfStack = array[0];
				} else {
					topOfStack = array[count - 1];
				}
				return topOfStack;
			}
		}

		/**
		 *     :           ()    
		 */

	}

	/**
	 *     ,         
	 * 
	 * @author nangua
	 */
	static class Operator {
		String value;
		//       -1
		int priority = -1;

		public Operator() {
		}

		public String getValue() {
			return value;
		}

		public void setValue(String value) {
			this.value = value;
			if (value.equals("+") || (value.equals("-"))) {
				this.priority = 1;
			} else if (value.equals("*") || (value.equals("/"))) {
				this.priority = 2;
			} else if (value.equals("(") || (value.equals(")"))) {
				this.priority = 3;
			} else if (value.equals("=")) {
				this.priority = 0;
			}
		}

		public int getPriority() {
			return priority;
		}

		public void setPriority(int priority) {
			this.priority = priority;
		}
	}
}

좋은 웹페이지 즐겨찾기