Sorting an array?

Question

Algorithms

Greetings!
I ask for help from the respected Habra community with the solution of such a problem:
In the process of writing a simple interpreter of mathematical expressions (so far even without brackets, banal expressions like 5+15*2/10+2^3 ) just 4 fun, as they say, ran into a problem...
I get an array of operations in an expression of the form position=>operation, which for the above example would be:

array(
    1   => '+',
    4   => '*',
    6   => '/'
    9   => '+',
    11 => '^',
)

I also have an array of operations priorities like

array(
    '+' => 1,
    '-' => 1,
    '*' => 2,
    '/' => 2,
    '^' => 3,
)

Now I would like to sort the operations by priority, but I’ve been slowing down all morning, I can’t think of an implementation ...
As a result, you need to get (for this example) the following array:

array(
    11 => '^',
    4 => '*',
    6 => '/',
    1 => '+',
    9 => '+',
)

I would be grateful for help in the form of an algorithm.

Answer 1

You have the wrong position initially. You need not to collect a linear array, but a tree of arguments and operators.

Answer 2

When viewing the expression, form an array of records where the value will be the structure of Priority and Operation. Further, by means of the language, sorting by the priority field should not be a problem (the usual passage of a function through an array).
In general, the ideal option is Reverse Polish notation .

Answer 3

I wrote a similar calculator, but with brackets. I asked myself such a test for a workshop when studying C. In my opinion, a bicycle is simpler than reverse Polish notation (it is also postfix) for such arithmetic has not yet been invented. Everything else is a complication, giving more confusion than effectiveness.
For fun - look towards the Fort language. All arithmetic is postfix :)

Answer 4

Who prevents the structure [Priority, Operation] from inserting Position as well? But why do you need her?
You need to parse the entered expression into a form convenient for processing by recursion or a loop.
I would aim for something like this (for 5+15*2/10+2^3):

array(
  0 => '2^3',
  1 => '2/10',
  2 => '15*{1}',
  3 => '5+{2}',
  4 => '{3}+{0},
);

Such an array is traversed in one cycle with a simple switch. But yes, the question was the algorithm for such parsing =).

Answer 5

Make an array of operations with pre-known keys:

array(
    '^' => array(),
    '*' => array(),
    '/' => array(),
    '+' => array(),
    '-' => array(),
);

And then fill it with the found positions. Then just loop through it from top to bottom. Another thing is that the positions are also somehow frivolous. It may be better to collect the elements of the expression on a stack and use not the position in the expression, but the number of the element on the stack.

Answer 6

Form
an array(
1 => 1,
4 => 2,
6 => 2,
9 => 1,
11 => 3,
)
and sort it?
In general, it is better to read Dragon Book, there is about it.

Answer 7

You can try using a priority queue (popularly referred to as a “heap”). In C++ it is called priority_queue, in java it is called PriorityQueue. You can organize each element of your array as a structure (or class) with two fields: position, operation. And overload the comparison operator (<) for the given class. Then, when parsing the expression, you will insert elements into this queue and they will be there in a sorted form. The complexity is equivalent to the complexity of sorting (insertion of each element will be done in O(log N), where N is the number of elements already in the queue).