6

How do you evaluate arbitrary math expressions using temporary variables instead of a stack? What I'm talking about is translating an expression into an array of simple operations- each that change one variable based on the second argument.

An example list of operations might be:

=
+=
-=
*=
/=

Notice how each operation changes the first argument. (none of them "return" anything)

Here's a simple expression: (I have postfix with depth written under it as well)

x=2+a*(b+c)
x 2 a b c + * + =
0 1 2 3 4 3 2 1 0


x=c
x+=b
x*=a
x+=2

Notice how you don't need temporary variables.

Here's an expression that requires a temporary variable:

x=a*(b+c)+d*(e+f)
x a b c + * d e f + * + =
0 1 2 3 2 1 2 3 4 3 2 1 0

x=b
x+=c
x*=a
tmp=e
tmp+=f
tmp*=d
x+=tmp

I can't seem to figure out an algorithmic solution for obtaining these sets of operations. Needing temporary variables seems to have something to do with lower-precedence operators that have the result of higher-precedence operators as arguments, but I can't tell.

I feel stupid... The way seems right in front of me but I can't see it. Obviously you could do it the "easy" way; AKA, make a temporary variable to store the result of each operation so no operations are destructive to anything but what you put before the =, but that's bad and I don't like it. How can you get the "algorithm" for an expression in simplest form?

EDIT: Due to my own ambiguity, I must clarify that a stack is allowed in translation, but not in the end psuedo-language I'm producing.

Improve this question
6
  • How about an array? Commented Jan 2, 2013 at 3:00
  • The issue I have is that I'm working on a "platform" that does not take to arrays and stacks nicely- it's possible to use them but it's ridiculously expensive to do so, and using temp variables (or more descriptively dedicated temporary addresses) is orders of magnitude faster. (and yes, this is just something I'm doing as a timewaster :P) Commented Jan 2, 2013 at 3:11
  • 1
    If your "platform" allows you to make function calls, just nest function calls to create a stack under the covers (all languages must store the return address of the function call, and it's usually stored on the stack). Commented Jan 2, 2013 at 3:41
  • It doesn't- I'm currently thinking about the logistics of making a human-readable-language to BF translator; that's why this question came up. Functions would end up being macros due to ONLY having loops- this as a result means no recursion either. Of course, the language is Turing Complete, so theoretically you could make it evaluate recursive functions, it's just far beyond what I want to make here. Commented Jan 2, 2013 at 3:50
  • From your question is not clear where and when the expression-translation is going to take place. Will it take place on your "platform", so stacks and recursion are "forbidden" already for that step? Or do you just want to happen the final evaluation of the translated expression without a stack? Please clarify! Commented Jan 2, 2013 at 17:33

4 Answers 4

Reset to default
5

Here is a suggestion.

Create a parse tree. Reorder it so that the deepest part of the tree is to the left, and do this recursively.

Every "rising chain" in the parse tree does not need temporaries. Every time you encounter a node with children on both sides, you will need a temporary. If you process the whole tree, you can discover the maximum number of temporaries that you need at any given time.

I have not tried to show that this greedy solution is truly optimal, but it discovers the best answer in simple cases, and in all cases you'll come up with an answer with a limited number of temporaries.

Improve this answer
4
  • I remember thinking briefly about something similar to this earlier, but I had no idea if it would actually work. I should have tried it first instead of forgetting about it. Thanks! EDIT: I'll wait a day or two before selecting this as the answer. Commented Jan 2, 2013 at 6:46
  • How would you do recursion without a stack? Commented Jan 2, 2013 at 11:16
  • @Blrfl, I think the idea is to use a more powerful machine as the compiler. Commented Jan 2, 2013 at 12:42
  • @Blrfl: see my comment below the question, the OP was not clear if he does not want a stack already for the translation or just for the evaluation of the expressions. Commented Jan 2, 2013 at 17:35
4

Here's a way:

Start with your expression:

x=2+a*(b+c)

Write out the stack operations that would be used:

PUSH b
PUSH c
ADD
PUSH a
MULTIPLY
PUSH 2
ADD
STORE x

Replace PUSH followed by a math operation by an inplace math operation

PUSH b
IADD c
IMULTIPLY a
IADD 2
STORE x

Simply use variables and temps for each position on the stack. The first position will be x, and the rest will be temps

x = b
x += c
x *= a
x += 2
Improve this answer
2

If I'm understanding your problem correctly, look at the algorithms used by compiler to compile expressions for machines with registers while trying to use as few registers as possible. For instance this one is a classic, more modern approaches are using graph coloring.

Improve this answer
5
  • Actually, real-world compilers rarely use graph coloring because it's just too damn slow (NP-compile). Instead, every register allocator I've seen uses some heuristic (e.g. linear scan). Commented Jan 2, 2013 at 16:31
  • @delnan, my understanding was that compilers where expressing the problem as a (modified, there is sometimes the need to spill registers) graph coloring one (which allow to express some other constraints such as the fact that the value of a register is destroyed as side effect of some instruction) and then used heuristic to solve it in an acceptable time. Commented Jan 2, 2013 at 16:40
  • That's kind of correct in that someone who devises a register allocator probably thinks in terms of graph coloring at least part of the time. But saying the resulting compiler is "using graph coloring" is like saying a GPU is solving the rendering equation. It's overstating what actually happens by mixing up the knowledge of the programmer with the implemented algorithm. I'm likely too harsh, I'm just rather tired of that meme and related ones. Commented Jan 2, 2013 at 16:46
  • @delnan, I'm pretty sure that's the term used by people in the trade for that class of algorithms. The chapter "Register allocation" of "Advanced compiler design implementation" has two sections ("graph coloring" and "priority-based graph coloring") using the term and that's the only named approaches at that level (the other sections describing methods are titled "local methods" and "other approaches", together they span 3 pages, while the graph coloring titled one span 40 pages) and google scholar finds about 5000 references with titles like "Register allocation via graph coloring". Commented Jan 2, 2013 at 18:47
  • Possible, it's just contrary to my observations (note that I'm talking about heuristics which are actually used in real-world compilers, not simply about any register allocator). As a counter-examples, a LLVM guy didn't mention graph coloring, and a paper about linear scan says it's "not based on graph coloring". Every time I encountered, it was general introduction to the topic, often immediately followed by "but we don't do that because it's slow". Commented Jan 2, 2013 at 18:58
0

So this would be a problem:

x=(a*b)+(c*d)

Assuming neither a nor b is zero, then factor out the (a*b) term:

x = (1+(c*d)/(a*b))*(a*b)

So:

x=c
x*=d
x/=a
x/=b
x+=1
x*=a
x*=b

As I said, if a or b is zero, you have to pre-reduce the calculation to:

x=c*d
Improve this answer
3
  • 1
    This assumes operation over a field, which isn't stated in the question and is unlikely in practice (as neither the integers nor IEEE-854 floating point representations are fields). Commented Jan 2, 2013 at 19:26
  • @PeterTaylor - I don't think I'm grokking what you're saying. Can you explain a bit more? Commented Jan 2, 2013 at 19:48
  • The approach of factoring out the a*b term works mathematically, assuming that we're using real numbers, rational numbers, or something structurally similar. But it wouldn't necessarily give the same result if we're using float, and it certainly wouldn't give the same result if we're using int (e.g. 7/2*2 gives 6). The question doesn't say what it's using, but from the comments it's definitely using int. Commented Jan 2, 2013 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.