Sorting an array?


Warning: count(): Parameter must be an array or an object that implements Countable in /home/styllloz/public_html/qa-theme/donut-theme/qa-donut-layer.php on line 274
0 like 0 dislike
47 views
Welcome!


Asking for help from a respected Abrasheva to the decision of such tasks:


In the process of writing a simple interpreter for mathematical expressions (so far, even without parentheses, the banal expressions such as 5+15*2/10+2^3) just 4 fun, as they say, faced with the problem...


I get the array of operations in terms of position=>operation, which for the above example would be:
array( 1 => '+', 4 => '*', 6 => '/' 9 => '+', 11 => '^', )


I also have an array of priorities of operations of the form
array( '+' => 1, '-' => 1, '*' => 2, '/' => 2, '^' => 3, )


Now to sort transactions by priority, but that's something inhibit all morning, can't think of the...


In the end we need to (for this example) the following array:
array( 11 => '^', 4 => '*', 6 => '/', 1 => '+', 9 => '+', )


I would be grateful for assistance in the form of an algorithm.
by | 47 views

7 Answers

0 like 0 dislike
You have the wrong position initially. You need not a linear array to collect, and the tree of arguments and operators.
by
0 like 0 dislike
When viewing expressions to generate an array of records where the value will be a Priority structure and Operation. Further, by means of the language to sort on the field the priority should not be a problem (the usual pass the function the array).
\r
In General, the ideal Reverse Polish notation.
by
0 like 0 dislike
Wrote a similar calculator, but with parentheses. Asked myself a test lab when learning C. In my opinion easier bike than reverse Polish notation (it is the same Postfix) for such arithmetic had not yet been invented. Everything else is complication, which gives more confusion than efficiency.
For fun — view toward language Fort. There all arithmetic Postfix :)
by
0 like 0 dislike
Who interferes in the structure [Priority Operation] itility and Position? Although why is it you?
You need to parse the expression you entered in easy to handle recursion or a loop shape.
I would aspire to such an entry (for 5+15*2/10+2^3):
\r
array( 0 => '2^3', 1 => '2/10', 2 => '15*{1}', 3 => '5+{2}', 4 => '{3}+{0}, ); 

Such an array is traversed one cycle with a simple switch. But Yes, the question was the algorithm of this review =).
by
0 like 0 dislike
To make array operations with known keys:
\r
array( '^' => array(), '*' => array(), '/' => array(), '+' => array(), '-' => array(), );

And then it was found to fill positions. Then just in a loop passing through it from top to bottom. Another thing that is somehow frivolous. It may be better to gather the elements of the expression stack and use the position in the expression, and the element number in the stack.
by
0 like 0 dislike
To form
array(
1 => 1,
4 => 2,
6 => 2,
9 => 1,
11 => 3,
)
and sort it?
In General, better Dragon Book to read, there about it is.
by
0 like 0 dislike
You can try to use a priority queue (it is still called "heap"). In C++ it's called priority_queue, java PriorityQueue. You can organize each element of your array in a structure (or class) with two fields: position, surgery. And to overload a comparison operator (<) for this class. Then when you parse the expression you insert items into this queue and there they will be in sorted form. Complexity equivalent to the complexity of sorting (insert each element will be O(log N), where N is the number of elements already in the queue).
by

Related questions

0 like 0 dislike
1 answer
asked Jun 14, 2019 by megamage
0 like 0 dislike
2 answers
asked Jun 1, 2019 by keddad
0 like 0 dislike
5 answers
0 like 0 dislike
1 answer
0 like 0 dislike
1 answer
110,608 questions
257,186 answers
0 comments
27,873 users