Leedcode2-后缀表达式结果-白红宇

Leedcode2-后缀表达式结果

阅读量：802 次

发布时间：2023-01-30

本文共 1745 字，大约阅读时间需要 5 分钟。

evaluation of arithmetic expressions. The valid operators include addition, subtraction, multiplication, and division. Each operand can be either an integer or another expression.

Examples

The expression ["2", "1", "+", "3", "*"] evaluates to ((2 + 1) * 3), resulting in 9. Similarly, the expression ["4", "13", "5", "/", "+"] evaluates to (4 + (13 / 5)), which equals 6.

Compiler Implementation

The implementation of the compiler involves two main approaches: Forward Analysis and Backward Analysis.

Forward Analysis

Traverse the expression from left to right.

Maintain a stack to store intermediate results.

For each operator, apply it to the top of the stack and the current operand.

Example: ["2", "1", "+", "3", "*"]
- Traverse 2, push to stack.
- Traverse 1, push to stack.
- Traverse "+", pop 1 and 2, compute 3, push result.
- Traverse 3, push to stack.
- Traverse "*", pop 3 and 3, compute 9, push result.

Backward Analysis

Traverse the expression from right to left.

Use a stack to store intermediate results.

For each operator, pop operands from the stack and apply the operator.

Example: ["4", "13", "5", "/", "+"]
- Traverse 4, push to stack.
- Traverse 13, push to stack.
- Traverse "5", push to stack.
- Traverse "/", pop 5 and 13, compute 2.6, push result.
- Traverse "+", pop 2.6 and 4, compute 6.6, push result.