C++csp-J初赛2

1 有穷性：一个算法包括有限的操作步骤，能在执行有限的步骤后结束

2 可行性：算法中的每一个步骤都可以在有限时间内完成的基本操作，并得到确定的结果

3 确定性：算法中的每一个步骤都是确定的，不可模棱两可

4 时间复杂度：常数$O(1)$ 对数阶$O(logn)$ 线性阶$O(n)$ 线性对数阶$O(nlogn)$ 平方阶$O(n^2)$ 立方阶$O(n^3)$ 指数阶$O(2^n)$ 阶乘阶$O(n!)$

附图：

从右到左扫描表达式，遇到数字时直接入栈，遇到运算符时弹出栈顶两个数。

根据运算符对两个数进行相应计算，并将计算结果入栈。

重复上述过程直至表达式的最左端，剩余最后一个数在栈中弹出即为最终计算结果。

例如，表达式 (3+4)×5-6 的前缀表达式为 - × + 3 4 5 6

后缀表达式的计算步骤如下：

从左到右扫描表达式，遇到数字时直接入栈，遇到运算符时弹出栈顶两个数。

根据运算符对两个数进行相应计算，并将计算结果入栈。

重复上述过程直至表达式的最右端，剩余最后一个数在栈中弹出即为最终计算结果。

例如，表达式 (3+4)×5-6 的后缀表达式为 3 4 + 5 × 6 -

初始化两个栈：运算符栈和储存中间结果的栈。

从右至左扫描中缀表达式。

遇到操作数时，将其压入储存中间结果的栈。

遇到运算符时，比较其与运算符栈顶运算符的优先级： 如果运算符栈为空，或栈顶运算符为右括号，则直接将此运算符入栈。 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入运算符栈。 否则，将运算符栈顶的运算符弹出并压入到储存中间结果的栈中，再次比较。

遇到括号时： 如果是右括号，则直接压入运算符栈。 如果是左括号，则依次弹出运算符栈顶的运算符，并压入储存中间结果的栈，直到遇到右括号为止。

重复上述步骤，直到表达式的最左边。

将运算符栈中剩余的运算符依次弹出并压入储存中间结果的栈。

依次弹出储存中间结果的栈中的元素并输出，结果即为前缀表达式。

初始化两个栈：运算符栈和储存中间结果的栈。

从左至右扫描中缀表达式。

遇到操作数时，将其压入储存中间结果的栈。

遇到运算符时，比较其与运算符栈顶运算符的优先级： 如果运算符栈为空，或栈顶运算符为左括号，则直接将此运算符入栈。 否则，若优先级比栈顶运算符的高，也将运算符压入运算符栈。 否则，将运算符栈顶的运算符弹出并压入到储存中间结果的栈中，再次比较。

遇到括号时： 如果是左括号，则直接压入运算符栈。 如果是右括号，则依次弹出运算符栈顶的运算符，并压入储存中间结果的栈，直到遇到左括号为止。

重复上述步骤，直到表达式的最右边。

将运算符栈中剩余的运算符依次弹出并压入储存中间结果的栈。

依次弹出储存中间结果的栈中的元素并输出，结果即为后缀表达式。