Arithmetic evaluation: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Hout (talk | contribs)
9,660 edits
→‎{{header|Haskell}}: Added a type signature to expr
→‎{{header|Java}}: code cleanup, consistent indentation
Line 2,611: Line 2,611:
<lang java>import java.util.Stack;
<lang java>import java.util.Stack;


public class ArithmeticEvaluation
public class ArithmeticEvaluation {

{
public static enum Parentheses { LEFT, RIGHT }
public interface Expression {
BigRational eval();
public static enum BinaryOperator
{
ADD('+', 1) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.add(rightValue); }
},
SUB('-', 1) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.subtract(rightValue); }
},
MUL('*', 2) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.multiply(rightValue); }
},
DIV('/', 2) {
public BigRational eval(BigRational leftValue, BigRational rightValue) { return leftValue.divide(rightValue); }
};
public final char symbol;
public final int precedence;
BinaryOperator(char symbol, int precedence)
{
this.symbol = symbol;
this.precedence = precedence;
}
}

public enum Parentheses {LEFT}
public abstract BigRational eval(BigRational leftValue, BigRational rightValue);

}
public enum BinaryOperator {
ADD('+', 1),
public static class BinaryExpression
SUB('-', 1),
{
MUL('*', 2),
public Object leftOperand = null;
DIV('/', 2);
public BinaryOperator operator = null;

public Object rightOperand = null;
public final char symbol;
public final int precedence;
public BinaryExpression(Object leftOperand, BinaryOperator operator, Object rightOperand)

{
BinaryOperator(char symbol, int precedence) {
this.leftOperand = leftOperand;
this.operator = operator;
this.symbol = symbol;
this.rightOperand = rightOperand;
this.precedence = precedence;
}

public BigRational eval(BigRational leftValue, BigRational rightValue) {
switch (this) {
case ADD:
return leftValue.add(rightValue);
case SUB:
return leftValue.subtract(rightValue);
case MUL:
return leftValue.multiply(rightValue);
case DIV:
return leftValue.divide(rightValue);
}
throw new IllegalStateException();
}

public static BinaryOperator forSymbol(char symbol) {
for (BinaryOperator operator : values()) {
if (operator.symbol == symbol) {
return operator;
}
}
throw new IllegalArgumentException(String.valueOf(symbol));
}
}
}

public BigRational eval()
public static class Number implements Expression {
private final BigRational number;
{

BigRational leftValue = (leftOperand instanceof BinaryExpression) ? ((BinaryExpression)leftOperand).eval() : (BigRational)leftOperand;
public Number(BigRational number) {
BigRational rightValue = (rightOperand instanceof BinaryExpression) ? ((BinaryExpression)rightOperand).eval() : (BigRational)rightOperand;
this.number = number;
return operator.eval(leftValue, rightValue);
}

@Override
public BigRational eval() {
return number;
}

@Override
public String toString() {
return number.toString();
}
}
}

public static class BinaryExpression implements Expression {
public String toString()
public final Expression leftOperand;
{ return "(" + leftOperand + " " + operator.symbol + " " + rightOperand + ")"; }
public final BinaryOperator operator;
}
public final Expression rightOperand;

public static void createNewOperand(BinaryOperator operator, Stack<Object> operands)
public BinaryExpression(Expression leftOperand, BinaryOperator operator, Expression rightOperand) {
{
this.leftOperand = leftOperand;
Object rightOperand = operands.pop();
this.operator = operator;
operands.push(new BinaryExpression(operands.pop(), operator, rightOperand));
this.rightOperand = rightOperand;
return;
}
public static Object createExpression(String inputString)
{
int curIndex = 0;
boolean afterOperand = false;
Stack<Object> operands = new Stack<Object>();
Stack<Object> operators = new Stack<Object>();
inputStringLoop:
while (curIndex < inputString.length())
{
int startIndex = curIndex;
char c = inputString.charAt(curIndex++);
if (Character.isWhitespace(c))
continue;
if (afterOperand)
{
if (c == ')')
{
Object operator = null;
while (!operators.isEmpty() && ((operator = operators.pop()) != Parentheses.LEFT))
createNewOperand((BinaryOperator)operator, operands);
continue;
}
}

afterOperand = false;
@Override
for (BinaryOperator operator : BinaryOperator.values())
{
public BigRational eval() {
if (c == operator.symbol)
BigRational leftValue = leftOperand.eval();
BigRational rightValue = rightOperand.eval();
{
return operator.eval(leftValue, rightValue);
while (!operators.isEmpty() && (operators.peek() != Parentheses.LEFT) && (((BinaryOperator)operators.peek()).precedence >= operator.precedence))
}
createNewOperand((BinaryOperator)operators.pop(), operands);

operators.push(operator);
continue inputStringLoop;
@Override
}
public String toString() {
return "(" + leftOperand + " " + operator.symbol + " " + rightOperand + ")";
}
}
throw new IllegalArgumentException();
}
if (c == '(')
{
operators.push(Parentheses.LEFT);
continue;
}
afterOperand = true;
while (curIndex < inputString.length())
{
c = inputString.charAt(curIndex);
if (((c < '0') || (c > '9')) && (c != '.'))
break;
curIndex++;
}
operands.push(BigRational.valueOf(inputString.substring(startIndex, curIndex)));
}
}

private static void createNewOperand(BinaryOperator operator, Stack<Expression> operands) {
while (!operators.isEmpty())
Expression rightOperand = operands.pop();
{
Object operator = operators.pop();
Expression leftOperand = operands.pop();
operands.push(new BinaryExpression(leftOperand, operator, rightOperand));
if (operator == Parentheses.LEFT)
throw new IllegalArgumentException();
createNewOperand((BinaryOperator)operator, operands);
}
}

Object expression = operands.pop();
public static Expression parse(String input) {
if (!operands.isEmpty())
throw new IllegalArgumentException();
int curIndex = 0;
boolean afterOperand = false;
return expression;
Stack<Expression> operands = new Stack<>();
}
Stack<Object> operators = new Stack<>();
while (curIndex < input.length()) {
public static void main(String[] args)
int startIndex = curIndex;
{
char c = input.charAt(curIndex++);
String[] testExpressions = { "2+3", "2+3/4", "2*3-4", "2*(3+4)+5/6", "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", "2*-3--4+-.25" };

for (String testExpression : testExpressions)
if (Character.isWhitespace(c))
{
continue;
Object expression = createExpression(testExpression);

System.out.println("Input: \"" + testExpression + "\", AST: \"" + expression + "\", eval=" + (expression instanceof BinaryExpression ? ((BinaryExpression)expression).eval() : expression));
if (afterOperand) {
if (c == ')') {
Object operator;
while (!operators.isEmpty() && ((operator = operators.pop()) != Parentheses.LEFT))
createNewOperand((BinaryOperator) operator, operands);
continue;
}
afterOperand = false;
BinaryOperator operator = BinaryOperator.forSymbol(c);
while (!operators.isEmpty() && (operators.peek() != Parentheses.LEFT) && (((BinaryOperator) operators.peek()).precedence >= operator.precedence))
createNewOperand((BinaryOperator) operators.pop(), operands);
operators.push(operator);
continue;
}

if (c == '(') {
operators.push(Parentheses.LEFT);
continue;
}

afterOperand = true;
while (curIndex < input.length()) {
c = input.charAt(curIndex);
if (((c < '0') || (c > '9')) && (c != '.'))
break;
curIndex++;
}
operands.push(new Number(BigRational.valueOf(input.substring(startIndex, curIndex))));
}

while (!operators.isEmpty()) {
Object operator = operators.pop();
if (operator == Parentheses.LEFT)
throw new IllegalArgumentException();
createNewOperand((BinaryOperator) operator, operands);
}

Expression expression = operands.pop();
if (!operands.isEmpty())
throw new IllegalArgumentException();
return expression;
}

public static void main(String[] args) {
String[] testExpressions = {
"2+3",
"2+3/4",
"2*3-4",
"2*(3+4)+5/6",
"2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10",
"2*-3--4+-.25"};
for (String testExpression : testExpressions) {
Expression expression = parse(testExpression);
System.out.printf("Input: \"%s\", AST: \"%s\", value=%s%n", testExpression, expression, expression.eval());
}
}
}
}
}</lang>
}</lang>


{{out}}
{{out}}
<pre>Input: "2+3", AST: "(2 + 3)", eval=5
<pre>Input: "2+3", AST: "(2 + 3)", value=5
Input: "2+3/4", AST: "(2 + (3 / 4))", eval=11/4
Input: "2+3/4", AST: "(2 + (3 / 4))", value=11/4
Input: "2*3-4", AST: "((2 * 3) - 4)", eval=2
Input: "2*3-4", AST: "((2 * 3) - 4)", value=2
Input: "2*(3+4)+5/6", AST: "((2 * (3 + 4)) + (5 / 6))", eval=89/6
Input: "2*(3+4)+5/6", AST: "((2 * (3 + 4)) + (5 / 6))", value=89/6
Input: "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", AST: "((2 * ((3 + ((4 * 5) + ((6 * 7) * 8))) - 9)) * 10)", eval=7000
Input: "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", AST: "((2 * ((3 + ((4 * 5) + ((6 * 7) * 8))) - 9)) * 10)", value=7000
Input: "2*-3--4+-.25", AST: "(((2 * -3) - -4) + -1/4)", eval=-9/4</pre>
Input: "2*-3--4+-.25", AST: "(((2 * -3) - -4) + -1/4)", value=-9/4</pre>


=={{header|JavaScript}}==
=={{header|JavaScript}}==
Retrieved from "https://rosettacode.org/wiki/Arithmetic_evaluation"