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.

How to use the code

Input expressions as vectors of strings.

Use strlen to determine string lengths.

Use strtol or stod for type conversion of operands and results.

Status

The current implementation supports basic arithmetic operations and ensures correct computation of expressions. Further works can include:

Addition of floating-point numbers.

Handling of parentheses and operator precedence.

Error checking for invalid expressions.

转载地址：http://etgyk.baihongyu.com/

你可能感兴趣的文章

Objective-C实现萨内瓦片调度算法（附完整源码）