[SWEA]1223:計算機2(Java)

2442 ワード
データ構造 テキストリンク

質問する


SWE Expert Academy 1223計算機2[D 4]

に答える


スタックを使用して接尾辞式を作成/計算する問題
接尾辞フォーマットのコピー
数値の場合は直接出力します(接尾辞タグ文字列carrに格納されます). 
演算子の場合、pop/pushは優先度に応じてスタックに格納されます.
スタックに自己優先度より低い演算子が表示されるまでpop出力を続けます.
すなわち、すべての優先度が自己の演算子以上であるpop
現在の問題には+、*しかないため、+はスタック内のすべての演算子を出力し、*はpeek()値が*のときに出力します.
優先順位で演算子を出力した後、自分を押します.
接尾辞式の計算
文字列配列(carr)を巡回する.
数値の場合はスタックにプッシュ(以前とは異なるスタックを使用)し、演算子の場合は現在のスタックから2つの数値をポップアップして演算します.
演算後、結果を再プッシュします.
文字列の並べ替えが完了すると、スタックは結果値を1つだけ保存するので、結果を出力します.

コード#コード#

package stack;

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

public class Solution_d4_1223_계산기2 {
	static Stack<Character> stack ;
	static Stack<Integer> res ;
	static int n;
	static char[] carr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for(int T = 1 ; T<=10 ; T++) {
			n = Integer.parseInt(br.readLine());
			carr = new char[n];
			stack = new Stack<>();
			res = new Stack<>();
			toPostfix(br.readLine());
			sb.append("#").append(T).append(" ").append(Cal()).append("\n");			
		}
		System.out.println(sb.toString());
	}
    //후위표기식 계산
	private static int Cal() {
		for(int i =0 ; i < n ; i++) {
			if(carr[i] == '+') res.push(res.pop()+res.pop());
			else if(carr[i] == '*') res.push(res.pop()*res.pop());
			else res.push(carr[i]-'0');
		}
		return res.pop();
	}
    //후위표기식으로 변경
	private static void toPostfix(String str) {
		int idx =0;
		for(int i =0 ; i < n ; i++) {
			if(str.charAt(i)=='+' || str.charAt(i)=='*') {
				while(!stack.isEmpty() && canPop(str.charAt(i))) {
					carr[idx++] = stack.pop(); 
				}
				stack.push(str.charAt(i));
			}
			else carr[idx++] = str.charAt(i);
		}
		while(!stack.isEmpty()) carr[idx++] = stack.pop();
	}
    //우선순위 확인
	private static boolean canPop(char c) {	
		if(c == '+') return true;
		if(stack.peek() == '*') return true;
		else return false;
	}
}
[BOJ]6987号ワールドカップ(Java)
[C言語]Baekjun 9663:N-Queen