栈与计算器

栈是一个先进后出的一种数据结构
对于给定一个字符串计算其值，其字符串可能有三种：前，中和后缀表达式
而对于这三种表达式应该如何计算其值
中式表达式：（3+4）* 7-6 * 2
前缀表达式： - * + 3 4 7 * 6 2

• 1.首先从左向右压入栈s1
• 2.从s1栈顶读取遇到数字压入s2，遇到操作符从s2取出两个数字进行运算
• 3.重复以上操作，直到s1空，s2只有一个数字，这个数字即为结果

后缀表达式： 3 4 + 7 * 6 2 * -

• 1.从右向左压入栈s1
• 2.从s1栈顶读取遇到数字压入s2，遇到操作符从s2取出两个数字进行运算
• 3.重复以上操作，直到最后s2剩下的数字即为结果

中缀表达式转前缀表达式：

• 1 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
• 2 从右至左扫描中缀表达式；
• 3 遇到操作数时，将其压入S2；
• 4 遇到运算符时，比较其与S1栈顶运算符的优先级：
• （4-1） 如果S1为空，则直接将此运算符入栈；
• （4-2） 否则，若优先级比栈顶运算符的较高或相等(后缀表达式中是较高,没有相等)或栈顶运算符为右括号“)”，也将运算符压入S1；
• （4-3） 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
• 5 遇到括号时：
• （5-1） 如果是右括号“)”，则直接压入S1；
• （5-2） 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
• 6 重复步骤(2)至(5)，直到表达式的最左边；
• 7 将S1中剩余的运算符依次弹出并压入S2；
• 8 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
• (后缀表达式这里要将字符串反转输出,这里直接输出即可)

中缀表达式转后缀表达式：

• 1.初始化两个栈：运算符栈S1和储存中间结果的栈S2
• 2.从左至右扫描中缀表达式
• 3.遇到操作数时，将其压入S2
• 4.遇到运算符时，比较其与S1栈顶运算符的优先级：
• (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
• (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况)
• (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较
• 5.遇到括号时：
• (5-1) 如果是左括号“(”，则直接压入S1；
• (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃
• 6.重复步骤(2)至(5)，直到表达式的最右边
• 7.将S1中剩余的运算符依次弹出并压入S2
• 8.依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）