数式文字列を計算したい Stackの中身の型は決まっていない？

Question

数式文字列を計算したいです。
ネットで調べると逆ポーランド記法になおしてから計算するのが簡単なのかなと思い、それをやってみようと思いました。

StackとQueueを使うそうなのですが、数式には数値の部分と演算子(文字)の部分があって、どうやって一つのStackでその2つを扱うのかなと疑問が生まれました。

そもそもStackやQueueには中身の型は決まっていないんですか？

あと、数式文字列の計算するのにもっといい方法があれば教えて下さい。
とりあえず()+-*/が使えればいいです。ゆくゆくはsinとかも使えるようにしたいです。

よろしくお願いします。

Answer 1

全部やっても意味ないので簡単なRPN変換だけ。
関数とか考えたら切り出しはもうちょい工夫のし甲斐があると思います。

	public static void main(String[] args)
	{
		Queue<Object>	result;
		
		result = expressionToRpn("11*22 + 33/44 - 55");
		
		for(Object obj : result){
			System.out.print(obj.toString() + " ");
		}
		System.out.println();
	}

	public static Queue<Object> expressionToRpn(String exp)
	{
		LinkedList<Object>	rpn = new LinkedList<Object>();
		Stack<String>	op = new Stack<String>();
		int		p;
		
		p = 0;
		
		while(p < exp.length()){
			char	ch = exp.charAt(p);			
			
			if(Character.isDigit(ch)){
				int	v = 0;
				
				while(p < exp.length() && Character.isDigit(exp.charAt(p))){
					v = v * 10 + (exp.charAt(p) - '0');
					p++;
				}
				rpn.add(v);
			}else{
				if(ch == '+' || ch == '-' || ch == '*' || ch == '/'){
					while(!op.empty() && operatorPriority(op.peek()) >= operatorPriority(""+ch)){
						rpn.add(op.pop());
					}
					op.add(""+ch);
				}else if(Character.isSpace(ch) == false){
					throw new IllegalArgumentException("Illegal Character");
				}
				p++;
			}
			
		}
		
		while(!op.empty()){
			rpn.add(op.pop());
		}
		
		return rpn;
	}
	
	private static int operatorPriority(String op)
	{
		switch(op){
			case "+":	return 1;
			case "-":	return 1;
			case "*":	return 2;
			case "/":	return 2;
			default:	throw new IllegalArgumentException("Unknown Operator");
		}
	}

Comments

[akamakku]

丁寧にありがとうございます！！！
パッと見て、ほほぉと理解できるほど自分のJava力はありませんので今晩読み込みたいと思います(笑)

Answer 2

StackやQueueは指定された型から派生したクラスしか入れられないので、簡単なのはQueue<String>として数字の場合でもとりあえず文字列のまま入れるか、Queue<Object>で数字をIntegerなどのオブジェクトにしてIntegerとStringを混在させる方法です。
Stackは演算子と関数名しか入らないのでStack<String>でいいかと。

もっと凝った方法にするなら共通の基底クラスから数値や演算子のクラスを派生してその基底クラスをQueue/Stackに入れていく方法もありますが、とりあえず最初は↑で作ってみるのがいいと思います。

Comments

[akamakku]

Queue<Object>を使うとして、
その場合、トークンの数だけその都度オブジェクトを生成するのでしょうか。

具体的にどのようにするのか、その部分だけても教えていただけるととても嬉しいです。