0

In a coding problem I've been working on for some time now, I've come to a step where I have to evaluate a mathematical expression that looks like this :

3 * 2 ^ 3 ^ 2 * 5

and should be evaluated like this :

3 * 2 ^ 3 ^ 2 * 5 = 3 * 2^(3 * 2) * 5 = 3 * 64 * 5 = 960.

In the current form of my implementation, I have two vectors, one contains the operands as integers, while the other one contains the operators as chars.

For the current case, they would be : vector<int> operands = { 3, 2, 3, 2, 5 } and vector<char> operators = { '*', '^', '^', '*' }.

This is just a sample case, the order of operations may differ in the sense that multiplication might not always be the first/last operation to be performed.

I've been stuck at this particular step for a while now, namely evaluating the expression encapsulated by the two vector containers to an integer. I've looked at some mathematical parsers I could find on the web, but I still don't see how to implement a proper evaluation.

A solution would be very much appreciated.

enter image description here

plasmacel
  • 8,183
  • 7
  • 53
  • 101
user43389
  • 721
  • 6
  • 18
  • 1
    Do you really mean `2^(3 * 2)` and not `2^(3^2)`? – Robert Prévost Sep 30 '16 at 00:31
  • 1
    No, this is actually the expression form the problem imposes, couldn't do a lot about that. 2 ^ 3 ^ 2 should be regarded as 2 ^ (3 * 2) = 2 ^ 6, more generally y ^ x1 ^ x2 ^ ... ^ xn = y ^ (x1 * x2 * .... * xn). – user43389 Sep 30 '16 at 00:34
  • @user43389 No, 2^3^2 should be evaluated as 2^(3^2), = 2^9 = 512, and note that it is right-associative. What you wrote doesn't make sense. – user207421 Sep 30 '16 at 00:39
  • 1
    I'm not saying it makes mathematical sense, I just stated before that this is the evaluation required in this problem. – user43389 Sep 30 '16 at 00:41
  • And instead of downvoting, you could very well ask for a clarification if you don't understand what's being asked. – user43389 Sep 30 '16 at 00:41
  • Why does `^` once evaluate to `^` and another time to `*`? – plasmacel Sep 30 '16 at 00:44
  • 1
    It doesn't make any sense, not just mathematical sense. There are inconsistent uses of ^ in the expression. You will have to write a context-sensitive parser, and you will need to get a very precise definition of when ^ becomes *. It is infinitely more probable that either you or your client has simply misunderstood. NB (a) I do understand what is being asked, to the extent that anybody can be said to understand self-contradictions, and (b) you have zero information as to who has downvoted your question. – user207421 Sep 30 '16 at 00:44
  • This is an algorithmic challenge on hackerrank and the inconsistent use of ^ in this expression could be simply regarded as following: In an expression of the form y ^ x1 ^ x2 ^ ... ^ xn , the value on the left side of the first ^ establishes the basis of exponentiation, while the other n - 1 '^' symbols generate the exponent through successive multiplication. The multiplication chain stops when a '*' sign is encountered right after the last factor of the exponent. – user43389 Sep 30 '16 at 00:49
  • @user43389 You can do such things with expression templates. https://en.wikipedia.org/wiki/Expression_templates – plasmacel Sep 30 '16 at 00:51
  • @EJP, it is infinitely more probable that you don't understand the question and resort to making rash judgments that have no basis whatsoever. Check the problem in the newly updated post, I've only replaced the '**' with '^'. – user43389 Sep 30 '16 at 00:55
  • 1
    It is infinitely more probable that hackerrank haven't got a clue actually. But then I've only been a compiler writer since 1976. – user207421 Sep 30 '16 at 01:00
  • @EJP The expression would be perfectly consistent if the `^` (or `**`) operator were left-associative. That just happens not to be the case, in mathematics or in Python. – Kyle Strand Sep 30 '16 at 01:21
  • So, yes, it appears hackerrank screwed up, but that *is* the question they have (inadvertently) posed. – Kyle Strand Sep 30 '16 at 01:21
  • @plasmacel Because `(x ^ y) ^ z == x ^ (y * z)`, and it appears that whoever wrote this question for hackerrank mistakenly believes that exponentiation is left-associative (like most other mathematical operators). – Kyle Strand Sep 30 '16 at 01:23
  • Its just syntax. People make up whatever syntax they like, and can define its meaning any way they like. That may not be the way *you* would do it. Tough. If is well defined syntax, it is easy to write a parser and evaluator for it. See http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769. Re OPs representation of operators and operands as alternating values in a vector: that's pretty limiting (maybe not for this problem). Imagine "-" as a unary operator; how would he represent that in his vector? – Ira Baxter Sep 30 '16 at 01:36

2 Answers2

1

What you would like is possible with expression templates. They make it possible to evaluate expressions in non-standard order and/or behavior - using them you can also define multiple meaning for the same operator in an expression.

plasmacel
  • 8,183
  • 7
  • 53
  • 101
1

Simply compute the value as you parse the expression, maintaining one variable for the final product and one for the current multiplicand (i.e. the current group of exponents with the corresponding base). Apply each exponential operand sequentially as you see it, thus performing left-associative exponentiation.

As an aside, I wouldn't bother storing the entire expression in some kind of vectorized format; I see no useful reason for doing so.

Kyle Strand
  • 15,941
  • 8
  • 72
  • 167
  • That's precisely what I did (in terms of thinking), but I seem to have messed the implementation somehow (it only works on the given test case). Good to know this is the way to go, an implementation would be really nice if you had the time. Thank you – user43389 Sep 30 '16 at 01:31
  • @user43389 What test cases does your implementation fail on? Since the entire left-associativity issue is **not** mentioned in the original problem, and we're only *assuming* that this is what's expected for the solution based on the test case itself, it's entirely possible that *the example test case* is simply incorrect. – Kyle Strand Sep 30 '16 at 01:33
  • Unfortunately, the test cases are hidden. But based on the number of successful submissions from other people, I guess the problem is indeed doable, even considering its poorly written text. – user43389 Sep 30 '16 at 01:37
  • @user43389 Well, have you tried submitting a solution that simply evaluates the expressions with correct mathematical precedence (i.e. with right-associative exponentiation)? – Kyle Strand Sep 30 '16 at 02:01
  • @user43389 I've never tried hackerrank; do you have a permalink to the question so I could try submitting a solution? – Kyle Strand Sep 30 '16 at 02:02