사 칙 연산 식 값 구하 기

27292 단어 데이터 구조
제목
계산 "9 + (3 - 1)× 3 + 10 / 2 문자열 의 값
2. 문제 풀이 사고
2.1 접미사 표현 법 (RPN):
괄호 가 필요 없 는 접미사 표현 식 입 니 다.규칙:      왼쪽 에서 오른쪽 까지 편리 한 표현 식 의 모든 숫자 와 기 호 는 숫자 를 만나면 스 택 에 들 어가 고 기 호 를 만나면 스 택 꼭대기 에 있 는 두 개의 숫자 를 스 택 에서 나 와 계산 하고 연산 결 과 는 스 택 에 들 어가 최종 결 과 를 얻 을 때 까지 합 니 다.
2.2 접미사 식 접미사 식
규칙: 왼쪽 에서 오른쪽으로 접미사 표현 식 의 모든 숫자 와 기 호 를 편리 하 게 출력 합 니 다. 숫자 라면 접미사 표현 식 의 일부분 이 됩 니 다.기호 라면 스 택 상단 기호 와 의 우선 순 위 를 판단 하고 오른쪽 괄호 나 우선 순위 가 스 택 상단 기호 보다 높 지 않 으 면 스 택 상단 요 소 를 순서대로 스 택 에서 나 와 출력 하고 현재 기 호 를 스 택 에 들 어가 최종 출력 접미사 표현 식 까지 입 니 다.
3. 자바 코드 구현
static String exp = "9 + (3-1) * 3 + 10 / 2";

public static void main(String[] args) {
	List<String> strings = splitExp(exp);
	List<String> rights = mid2Right(strings);

	Stack<String> stack = new Stack<>();

	for (String str : rights) {
		if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
			BigDecimal a1 = new BigDecimal(stack.pop());
			BigDecimal a2 = new BigDecimal(stack.pop());
			if (str.equals("+")) {
				stack.push(a2.add(a1).toString());
			} else if (str.equals("-"))  {
				stack.push(a2.subtract(a1).toString());
			} else if (str.equals("*"))  {
				stack.push(a2.multiply(a1).toString());
			} else {
				stack.push(a2.divide(a1).toString());
			}
		} else {
			stack.push(str);
		}
	}
	System.out.println(stack.pop());
}

/**
 *      
 *
 * @param list
 * @return
 */
private static List<String> mid2Right(List<String> list) {
	List<String> rights = new ArrayList<>();
	Stack<String> stack = new Stack<>();
	for (String str : list) {
		if (str.equals("(")) {
			stack.push(str);
		} else if (str.equals("*") || str.equals("/")) {
			if (!stack.isEmpty()) {
				String pop = stack.pop();
				if (pop.equals("*") || pop.equals("/") || pop.equals("(")) {
					if (pop.equals("*") || pop.equals("/")) {
						rights.add(pop);
					}
				} else {
					stack.push(pop);
				}
			}
			stack.push(str);
		} else if (str.equals("+") || str.equals("-")) { //   +-     ,      (     
			while (!stack.isEmpty()) {
				String pop = stack.pop();
				if (pop.equals("(")) {
					stack.push(pop);
					break;
				} else {
					rights.add(pop);
				}
			}
			stack.push(str);
		} else if (str.equals(")")) { //      (     
			while (!stack.isEmpty()) {
				String pop = stack.pop();
				if (pop.equals("(")) {
					break;
				} else {
					rights.add(pop);
				}
			}
		} else {
			rights.add(str);
		}
	}

	while (!stack.isEmpty()) {
		rights.add(stack.pop());
	}
	return rights;
}

/**
 *            
 *
 * @param exp
 * @return
 */
private static List<String> splitExp(String exp) {
	List<String> list = new ArrayList<>();
	StringBuilder temp = new StringBuilder();
	for (char c : exp.toCharArray()) {
		if (c == ' ') {
			continue;
		}
		if (c == '+' || c == '-' || c == '/' || c == '*' || c == '(' || c == ')') {
			add(list, temp.toString());
			temp.setLength(0);
			add(list, String.valueOf(c));
		} else {
			temp.append(c);
		}
	}
	add(list, temp.toString());

	return list;
}

/**
 *     
 *
 * @param list
 * @param str
 */
private static void add(List<String> list, String str) {
	if (str.length() > 0) {
		list.add(str);
	}
}

좋은 웹페이지 즐겨찾기