Я однажды записал грубой силе поиск ключа RC5, который обработал два ключа за один раз, первый ключ использовал целочисленный конвейер, второй ключ использовал конвейеры SSE, и эти два были чередованы на уровне инструкции. Это было тогда вместе с программой супервизора, которая выполнила экземпляр кода каждого ядра в системе. Всего, код работал приблизительно в 25 раз быстрее, чем наивная версия C.
The algorithm is pretty simple (and here is a good explanation). Every operation has a binding weight, with + and - being the lowest. There are two rules:
Given your first example, 52+(1+2)*4-3, here is the stack:
52+ => +
52+( => + (
52+(1+ => + ( +
52+(1+2) => + //right parentheses popped +
52+(1+2)*4 => + *
52+(1+2)*4-3 => + - //can't put - on top of *, so pop off *
... and then pop the stack until it's empty.
Replacing your switch loop with the following (closest analog to what you had) will give correct answers for your three examples. In a real parser you would give each operator a weight and generalize the pop mechanism.
for (int i = 0; i < in.length; i++)
switch (in[i]) {
case '+':
case '-':
while (!stack.empty() && (stack.peek() == '*' || stack.peek() == '/')) {
out.append(' ');
out.append(stack.pop());
}
out.append(' ');
stack.push(in[i]);
break;
case '*':
case '/':
out.append(' ');
stack.push(in[i]);
break;
case '(':
stack.push(in[i]);
break;
case ')':
while (!stack.empty() && stack.peek() != '(') {
out.append(' ');
out.append(stack.pop());
}
stack.pop();
break;
default:
out.append(in[i]);
break;
}
Not an exact answer to the specific question but something I'd recommend for developing these kinds of algorithms: have a look at test driven devlopment (TDD). In brief: write a couple of unit tests - for example with JUnit - for the infix2 method, where you feed the method with test patterns (expressions) and test, if infix2 produces the right output.
Start with easy ones, like
assertequals("1", "1"); // positive number
assertequals("-1", "-1"); // negative number
assertequals("1+1", "1 1 +"); // simple addition
assertequals(" 1 + 1 ", "1 1 +"); // simple addition with whitechars
assertequals(" 1 + +1 ", "1 -1 +"); // simple addition with pos. number & whitechars
assertequals(" 1 + -1 ", "1 -1 +"); // simple addition with neg. number & whitechars
assertequals("(1+1)", "1 1 +"); // simple addition with brackets
and don't forget illegal expressions like
String[] illegalExpressions = {null, "", " ", "1 +", "1 + 1)"};
The test cases for you examples should be
assertequals("52+(1+2)*4-3", "52 1 2 + 4 * 3 -");
assertequals("52+((1+2)*4)-3", "52 1 2 + 4 * 3 -");
assertequals("(52+1+2)*4-3", "52 1 + 2 + 4 * 3 -");