Создать стек для преобразования из инфикса в постфикс с использованием массивов

Question

Я сейчас пытаюсь создать свой собственный стек без импорта java.util. *. Мне разрешено использовать массивы и циклы только для преобразования моего инфиксного выражения в постфикс, чтобы он работал в калькуляторе. Я уже могу разбить инфикс на термины, но не смог найти ни одной статьи, объясняющей, как решить эту проблему. Заранее спасибо!

Answer 1

здесь - хорошее описание алгоритма (wikipedia / en).

По сути, вы начинаете с разделения вашего выражения. Например,

a + b * c

Если это где строка, то вы делаете:

String expression = "a + b * c";
String[] terms = expression.split(" ");  // this will split the string at every whitespace

Теперь ваш массив должен выглядеть так: ["a", "+", "b", "*", "c"]

Теперь вам нужномассив, в который вы можете поместить свои «термины» для порядка постфиксов:

String[] postFixTerms = new String[expression.length]; // it should have the same size as the original array

Таким образом, чтобы заполнить его, вы читаете массив terms слева направо, то есть начинаете с индекса 0 и заканчиваетев п. но вы хотите отфильтровать операнды и поместить их в свой стек!

int termsIndex=0;  // you will have two indices because you have two arrays!
for(int i=0; i<terms.length; i++){
   String element = terms[i];
   if(elementIsOperand(element)){
      operandsStack.put(element);
   }else{
      postFixTerms[termsIndex] = element; 
      termsIndex++;
   }
}

На данный момент у вас должен быть массив с вашими "числами":

postFixTerms=["a", "b", "c", null, null]; // remember you only added the numbers in it not the operands, so there is still some space left at the end of the array

И у вас есть свой операндСтек:

operandsStack=["+","*"];

Теперь вам нужно только собрать их вместе, но помните, что стек работает "FILA" в первую очередь, поэтому:

postFixTerms[termsIndex] = operandsStack.pull();  // adds "*" first
termsIndex++;
postFixTerms[termsIndex] = operandsStack.pull();  // then adds the "+"

Если все пойдет правильно, ваше окончательное постфиксное выражение должно быть

["a","b","c","*","+"];