Using the following input string * + 16 4 + 3 1 and these instructions:
A prefix expression is where the operator comes first. For example, + 5 7 would be 12.
I am able to successfully generate the expected output of 80 with my current code, which I will post below. However, with another input string * + 16 * + 16 4 + 3 1 + 3 1 my output is 576, where it is expected to be 384. I'm not quite sure where I went wrong with my algorithm.
public class QueueUtils {
public static Queue<String> build(String line) {
Queue<String> queue = new LinkedList<>();
Scanner scanner = new Scanner(line);
while (scanner.hasNext())
{
String token = scanner.next();
queue.add(token);
}
return queue;
}
public static int eval(Queue<String> s)
{
List<String> list = new ArrayList<>(s);
List<String> operators = new ArrayList<>();
operators.add("+");
operators.add("-");
operators.add("*");
int n = eval(list, operators);
return n;
}
private static Integer eval(List<String> list, List<String> operators)
{
for (int i = 0; i < list.size(); i++)
{
String current = list.get(i);
String prev = null;
String next = null;
String nextNext = null;
if (i != 0)
{
prev = list.get(i - 1);
}
if (i != list.size() - 1)
{
next = list.get(i + 1);
}
if (i < list.size() - 2)
{
nextNext = list.get(i + 2);
}
if (operators.contains(prev) && prev != null)
{
if (!operators.contains(current)) {
int a = Integer.parseInt(current);
if (!operators.contains(next) && next != null) {
int b = Integer.parseInt(next);
Integer result = doOperation(prev, a, b);
list.remove(current);
list.remove(next);
list.add(i, result.toString());
eval(list, operators);
}
if (next == null)
{
list.remove(prev);
}
}
else
{
if (!operators.contains(next))
{
if (operators.contains(nextNext))
{
list.remove(current);
eval(list, operators);
}
}
}
}
else
{
if (operators.contains(current))
{
if (!operators.contains(next))
{
if (operators.contains(nextNext) || nextNext == null)
{
if (prev != null)
{
list.remove(current);
eval(list, operators);
}
}
}
}
}
}
return Integer.parseInt(list.get(0));
}
private static int doOperation(String operator, int a, int b)
{
int n = 0;
if (operator.equals("+"))
{
n = a + b;
}
else if (operator.equals("-"))
{
n = a - b;
}
else if (operator.equals("*"))
{
n = a * b;
}
return n;
}
}
Calling code:
public class Demo2 {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter an expression in prefix form (operator comes first)");
String line = keyboard.nextLine();
Queue<String> q = QueueUtils.build(line);
int result = QueueUtils.eval(q);
System.out.println(result);
}
}
So in order to solve this you need first need to reverse your input (so * + 16 * + 16 4 + 3 1 + 3 1 will become 1 3 + 1 3 + 4 16 + * 16 + *) and then use a bit of recursion to work your operations in groups of three.
So
1 3 + 1 3 + 4 16 + * 16 + *
4 4 20 * 16 + *
4 [80 16 + *] // we can't do anything with 4 4 20, so we just move on one.
4 [96 *]
4 96 *
384
Here's the code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class InputFunction {
private int doOperation(int a, int b, String operator) throws Exception {
int result;
if("+".equals(operator)){
result = a + b;
} else if("-".equals(operator)){
result = a - b;
} else if("*".equals(operator)){
result = a * b;
} else {
throw new Exception("Unsupported operator \"" + operator + "\"");
}
return result;
}
private List<String> evaluate(List<String> function) throws Exception {
List<String> processed = new ArrayList<>();
if(function.size() <= 2) {
return function;
} else {
for (int i = 0; i < function.size(); i += 3) {
String a = function.get(i);
if ((i + 1) < function.size()) {
String b = function.get(i + 1);
if ((i + 2) < function.size()) {
String c = function.get(i + 2);
if (a.matches("\\d+") && b.matches("\\d+") && !c.matches("\\d+")) {
processed.add(String.valueOf(doOperation(Integer.valueOf(a), Integer.valueOf(b), c)));
} else {
processed.add(a);
if(c.matches("\\d+")) {
processed.addAll(evaluate(function.subList(i + 1, function.size())));
break;
} else {
processed.add(b);
processed.add(c);
}
}
} else {
processed.add(a);
processed.add(b);
}
} else {
processed.add(a);
}
}
}
return evaluate(processed);
}
private void doFunction(String input) throws Exception{
List<String> function = Arrays.asList(input.split(" "));
Collections.reverse(function);
System.out.println(evaluate(function));
}
public static void main(String ... args) {
InputFunction inputFunction = new InputFunction();
try {
inputFunction.doFunction("+ + 5 5 + 5 5");
inputFunction.doFunction("* + 16 * + 16 4 + 3 1 + 3 1");
} catch (Exception e) {
e.printStackTrace();
}
}
}
... admit-ably I've not tried with any examples with a "-", but you should get the idea.