MyMain
public class MyMain {
public static void main(String args[]) {
if (args.length < 3) return;
Operator ope;
if (args[0].equals("add")) ope = new Addition();
else if (args[0].equals("sub")) ope = new Subtraction();
else return;
IntOperand op1 = new IntOperand(Integer.parseInt(args[1]));
IntOperand op2 = new IntOperand(Integer.parseInt(args[2]));
Expression exp = new Expression(ope, op1, op2);
System.out.println(exp.getValue());
}
}
Operator
public interface Operator {
public void setOperand1(Operand operand);
public void setOperand2(Operand operand);
public int calc();
}
Operand
public interface Operand {
public int getValue();
}
IntOperand
public class IntOperand implements Operand {
private int value;
public IntOperand(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
Expression
public class Expression implements Operand {
private Operator operator;
public Expression(Operator operator, Operand operand1, Operand operand2) {
this.operator = operator;
this.operator.setOperand1(operand1);
this.operator.setOperand2(operand2);
}
public int getValue() {
return operator.calc();
}
}
Addition
public class Addition implements Operator {
private Operand operand1;
private Operand operand2;
public void setOperand1(Operand operand) {
this.operand1 = operand;
}
public void setOperand2(Operand operand) {
this.operand2 = operand;
}
public int calc() {
return operand1.getValue() + operand2.getValue();
}
}
Subtraction
public class Subtraction implements Operator {
private Operand operand1;
private Operand operand2;
public void setOperand1(Operand operand) {
this.operand1 = operand;
}
public void setOperand2(Operand operand) {
this.operand2 = operand;
}
public int calc() {
return operand1.getValue() - operand2.getValue();
}
}
実行結果
L:\>java MyMain add 2 3
5
L:\>java MyMain sub 17 35
-18
MyMain
import java.util.*;
public class MyMain {
public static void main(String args[]) {
String exp = "(6 + 3) / (6 - 2) + 3 * 2 ^ 3 - 1";
Map<String, Integer> priMap = new HashMap<String, Integer>();
priMap.put("+", 1);
priMap.put("-", 1);
priMap.put("*", 2);
priMap.put("/", 2);
priMap.put("^", 3);
priMap.put("(", 5);
priMap.put(")", 0);
for (Integer i = 0; i <= 9; i++)
priMap.put(i.toString(), 4);
List<String> stack = new ArrayList<String>();
List<String> polish = new ArrayList<String>();
stack.add(" ");
priMap.put(" ", -1);
for (int i = 0; i < exp.length(); i++) {
String token = exp.substring(i, i+1);
if (token.trim().length() <= 0) continue;
Integer pri1 = priMap.get(token);
Integer pri2 = priMap.get(stack.get(stack.size() - 1));
if (pri1 == null) continue;
if (pri2 == null) continue;
while (pri1 <= pri2) {
if (stack.get(stack.size() - 1).equals("(")) break;
if (stack.size() > 0) {
polish.add(stack.get(stack.size() - 1));
stack.remove(stack.size() - 1);
pri2 = priMap.get(stack.get(stack.size() - 1));
if (pri2 == null) continue;
}
}
if (!token.equals(")")) {
stack.add(token);
} else {
stack.remove(stack.size() - 1);
}
}
for (int i = stack.size() - 1; i >= 0; i--) {
polish.add(stack.get(i));
}
System.out.print("与えられた式:");
System.out.println(exp);
System.out.print("逆ポーランド記法に変換後の式:");
for (int j = 0; j < polish.size(); j++)
System.out.print(polish.get(j));
System.out.println();
List<String> operandList = new ArrayList<String>();
for (int i = 0; i < polish.size(); i++) {
if(polish.get(i).matches("[0-9]*")) {
operandList.add(polish.get(i));
} else if (
(polish.get(i).equals("+"))
|| (polish.get(i).equals("-"))
|| (polish.get(i).equals("*"))
|| (polish.get(i).equals("/"))
|| (polish.get(i).equals("^"))
) {
IntOperand op1 = new IntOperand(Integer.parseInt(operandList.get(operandList.size() - 2)));
IntOperand op2 = new IntOperand(Integer.parseInt(operandList.get(operandList.size() - 1)));
Operator ope = null;
if (polish.get(i).equals("+")) ope = new Add();
else if (polish.get(i).equals("-")) ope = new Sub();
else if (polish.get(i).equals("*")) ope = new Mul();
else if (polish.get(i).equals("/")) ope = new Div();
else if (polish.get(i).equals("^")) ope = new Pow();
if (ope != null) {
Expression expr = new Expression(ope, op1, op2);
System.out.print(operandList.get(operandList.size() - 2));
System.out.print(polish.get(i));
System.out.print(operandList.get(operandList.size() - 1));
System.out.print("=");
System.out.println(expr.getValue());
operandList.set(operandList.size() - 2, Integer.toString(expr.getValue()));
}
operandList.remove(operandList.size() - 1);
}
}
System.out.print("答え:");
System.out.println(operandList.get(operandList.size() - 1));
}
}
Operand
public interface Operand {
public int getValue();
}
IntOperand
public class IntOperand implements Operand {
private int value;
public IntOperand(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
Expression
public class Expression implements Operand {
private Operator operator;
public Expression(Operator operator, Operand operand1, Operand operand2) {
this.operator = operator;
this.operator.setOperand1(operand1);
this.operator.setOperand2(operand2);
}
public int getValue() {
return operator.calc();
}
}
Operator
public abstract class Operator {
protected Operand operand1;
protected Operand operand2;
public void setOperand1(Operand operand) {
this.operand1 = operand;
}
public void setOperand2(Operand operand) {
this.operand2 = operand;
}
public abstract int calc();
}
Add
public class Add extends Operator {
public int calc() {
return operand1.getValue() + operand2.getValue();
}
}
Sub
public class Sub extends Operator {
public int calc() {
return operand1.getValue() - operand2.getValue();
}
}
Mul
public class Mul extends Operator {
public int calc() {
return operand1.getValue() * operand2.getValue();
}
}
Div
public class Div extends Operator {
public int calc() {
return operand1.getValue() / operand2.getValue();
}
}
Pow
public class Pow extends Operator {
public int calc() {
return (int)Math.pow(operand1.getValue(), operand2.getValue());
}
}
実行結果
L:\>java MyMain
与えられた式:(6 + 3) / (6 - 2) + 3 * 2 ^ 3 - 1
逆ポーランド記法に変換後の式:63+62-/323^*+1-
6+3=9
6-2=4
9/4=2
2^3=8
3*8=24
2+24=26
26-1=25
答え:25
step 3 前置記法を評価する
MyMain
public class MyMain {
public static void main(String args[]) {
String text = "(- (+ (/ (+ 6 3) (- 6 2)) (* 3 (^ 2 3))) 1)";
Node node = new ExpressionNode();
try {
node.parse(new Context(text));
System.out.print(node.toString() + " = ");
System.out.println(node.getValue());
} catch (Exception e) {
System.err.println(e);
}
}
}
class Context {
private int pos;
private String text;
private String currToken;
private int currTokenType;
private static final int LPAREN = 0;
private static final int ALPHA = 1;
private static final int OPERATOR = 2;
private static final int DIGIT = 3;
private static final int RPAREN = 4;
private static final int UNKNOWN = -1;
private static final String lparen = "(";
private static final String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
private static final String operator = "+-*/^";
private static final String digit = "0123456789";
private static final String rparen = ")";
public Context(String text) {
this.text = text;
pos = 0;
currToken = "";
currTokenType = UNKNOWN;
nextToken();
}
public String nextToken() {
int nextTokenType = UNKNOWN;
currTokenType = UNKNOWN;
while (pos < text.length()) {
char c = text.charAt(pos);
if (lparen.indexOf(c) >= 0) nextTokenType = LPAREN;
else if (alpha.indexOf(c) >= 0) nextTokenType = ALPHA;
else if (operator.indexOf(c) >= 0) nextTokenType = OPERATOR;
else if (digit.indexOf(c) >= 0) nextTokenType = DIGIT;
else if (rparen.indexOf(c) >= 0) nextTokenType = RPAREN;
else nextTokenType = UNKNOWN;
if (currTokenType == nextTokenType) {
if ((currTokenType != LPAREN) && (currTokenType != RPAREN)) {
if (nextTokenType != UNKNOWN) currToken += c;
pos++;
continue;
}
}
if (currTokenType == UNKNOWN) {
currTokenType = nextTokenType;
currToken = String.valueOf(c);
pos++;
} else {
return currToken;
}
}
return currToken;
}
public String currToken() {
return currToken;
}
public void skipToken(String token) throws Exception {
if (!token.equals(currToken)) {
throw new Exception(token + " が あるべきべきところに、" + currToken + " が ある");
}
nextToken();
}
}
abstract class Node {
public abstract void parse(Context context) throws Exception;
public abstract int getValue() throws Exception;
}
class ExpressionNode extends Node {
private OperatorNode operator;
private OperandNode operand1;
private OperandNode operand2;
public void parse(Context context) throws Exception {
context.skipToken("(");
operator = new OperatorNode();
operator.parse(context);
operand1 = new OperandNode();
operand1.parse(context);
operand2 = new OperandNode();
operand2.parse(context);
context.skipToken(")");
}
public String toString() {
return "(" + operator + " " + operand1 + " " + operand2 + ")";
}
public int getValue() throws Exception {
int n1 = operand1.getValue();
int n2 = operand2.getValue();
int result = 0;
if (operator.toString().equals("+")) result = n1 + n2;
else if (operator.toString().equals("-")) result = n1 - n2;
else if (operator.toString().equals("*")) result = n1 * n2;
else if (operator.toString().equals("/")) result = n1 / n2;
else if (operator.toString().equals("^")) result = (int)Math.pow(n1, n2);
return result;
}
}
class OperatorNode extends Node {
private String operator;
public void parse(Context context) throws Exception {
operator = context.currToken();
context.skipToken(operator);
}
public String toString() {
return operator;
}
public int getValue() throws Exception {
return 0;
}
}
class OperandNode extends Node {
private Node node;
public void parse(Context context) throws Exception {
if (context.currToken().equals("(")) {
node = new ExpressionNode();
} else {
node = new NumberNode();
}
node.parse(context);
}
public String toString() {
return node.toString();
}
public int getValue() throws Exception {
return node.getValue();
}
}
class NumberNode extends Node {
private String number;
public void parse(Context context) throws Exception {
number = context.currToken();
context.skipToken(number);
}
public String toString() {
return number;
}
public int getValue() throws Exception {
int value = 0;
try {
value = Integer.parseInt(number);
} catch (NumberFormatException e) {
System.err.println(e);
throw e;
}
return value;
}
}
実行結果
L:\>java MyMain
(- (+ (/ (+ 6 3) (- 6 2)) (* 3 (^ 2 3))) 1) = 25