大学生简历制作网站,给wordpress添加背景音乐,澄海建网站,做性视频网站有哪些逆波兰式背景介绍
逆波兰式是一种特殊的数学表达式表示法#xff0c;它的诞生背景可以追溯到20世纪30年代。当时#xff0c;波兰数学家Jan Wjtowicz和Wacław Sierpiński提出了一种新的数学表达式表示法#xff0c;这种表示法将运算符放在操作数之后#xff0c;而不是传统…逆波兰式背景介绍
逆波兰式是一种特殊的数学表达式表示法它的诞生背景可以追溯到20世纪30年代。当时波兰数学家Jan Wójtowicz和Wacław Sierpiński提出了一种新的数学表达式表示法这种表示法将运算符放在操作数之后而不是传统的数学表达式中的运算符放在操作数之前的表示法。 这种新的表示法被称为逆波兰式因为它与传统的波兰式数学表达式相反。传统的波兰式数学表达式是一种将运算符放在操作数之前的表示法例如(23)*4。而逆波兰式则是将运算符放在操作数之后例如2 3 4 *。
逆波兰式的出现主要是为了解决传统的数学表达式中的一些问题例如括号匹配问题。在传统的数学表达式中括号的嵌套顺序非常重要如果括号的嵌套顺序不正确就会导致计算结果错误。而逆波兰式则避免了括号的嵌套问题因为它不需要使用括号来表示运算顺序。 逆波兰式的出现对计算机科学产生了重要的影响它被广泛应用于计算机程序设计中特别是在函数式编程和函数式编译器中。逆波兰式也被用于一些高级编程语言中例如Lisp和Scheme。 前缀式、后缀式、中缀式的概念
二叉树表达
一个表达式可以使用一棵二叉树来进行一个存储表达而对应的前、中、后序遍历的结果对应的就是前缀式、中缀式、后缀式。
例如表达式**((ab)/(cd)p)-(cm)**
对应二叉树 中缀式
中缀式就是我们人能够认识的表达式格式如((ab)/(cd)p)-(cm)而对应的就是该二叉树的中序遍历得到的结果
前缀式
前缀式就是将该二叉树进行前序遍历得到的结果-/abcdpem
后缀式
后缀式就是将该二叉树进行后序遍历得到的结果abcd*/pem*-
总结
从前中后序的结构其实不难得出一个很明显的结论
前缀式往往会将运算符号放在前面数字放在后面而后缀式往往是将数字放在前面运算符号放在后面。
波兰式常见面试算法题
1.根据前缀式、后缀式求出表达式结果
后缀式求值leetcode地址https://leetcode.cn/problems/8Zf90G/
题目简单描述
根据[ 逆波兰表示法]求该后缀表达式的计算结果。有效的算符包括 、-、*、/ 。每个运算对象可以是整数也可以是另一个逆波兰表达式。说明整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。示例 1输入 tokens [2,1,,3,*]
输出 9
解释 该算式转化为常见的中缀算术表达式为((2 1) * 3) 9其实这个题型是特别简单的大概思路就是直接遍历tokens遇见数字就将其放入栈中遇见运算符将数字取出两个进行运算再将结果放入栈中…即便没遇见过也是很容易想出来的
Go代码展示
func evalRPN(tokens []string) int {stack : []int{}for _, token : range tokens {val, err : strconv.Atoi(token)if err nil {stack append(stack, val)} else {num1, num2 : stack[len(stack)-2], stack[len(stack)-1]stack stack[:len(stack)-2]switch token {case :stack append(stack, num1num2)case -:stack append(stack, num1-num2)case *:stack append(stack, num1*num2)default:stack append(stack, num1/num2)}}}return stack[0]
}
前缀式求值与其原理相同建议自己可以尝试一下不过leetcode没有类似题目
中缀式转前缀式、中缀式转后缀式
这种题型其实也挺常考的之前面试字节一面就出了一个中缀式转后缀式的算法题。。
这类题就没这么容易了因为有括号的原因所以其实需要考虑的情况是比较多的。不过基本原理依旧是使用栈~
此题我依旧只解析中缀转后缀的例子因为中缀转前缀原理依旧一致。
例如该中缀式((ab)/(cd)p)-(cm)
其基本原理依旧是遍历一遍中缀式对’(‘、’)、‘运算符’、数字’都会有不同的处理方式
case 1’数字’:直接将其放入结果数组
case 2 ‘(’: 放入栈中
case 3 ‘)’:将其与对应左括号之间的符号出栈放入结果数组
case 4 ‘运算符’:若在栈底, 在括号底, 或者操作符优先级比栈顶的高, 则操作符入栈否则出栈
举个例子((ab)/(cd)p)-(cm) ----abcd*/pcm*-
( -- stack[(] res[]
( -- stack[( , (] res[]
a -- stack[( , (] res[a]-- stack[( , ( , ] res[a]
b -- stack[( , ( , ] res[a,b]
) -- stack[(] res[a,b,]
/ -- stack[(,/] res[a,b,]
( -- stack[(,/,(] res[a,b,]
c -- stack[(,/,(] res[a,b, , c]
* -- stack[(,/,( , *] res[a,b, , c]
d -- stack[(,/,( , *] res[a,b, , c , d]
) -- stack[(,/] res[a,b, , c , d,*]-- stack[(,] res[a,b, , c , d,*,/]
p -- stack[(,] res[a,b, , c , d,*,/,p]
) -- stack[] res[a,b, , c , d,*,/,p,]
- -- stack[-] res[a,b, , c , d,*,/,p,]
( -- stack[-,(] res[a,b, , c , d,*,/,p,]
c -- stack[-,(] res[a,b, , c , d,*,/,p,,c]* -- stack[-,(,*] res[a,b, , c , d,*,/,p,,c]m -- stack[-,(,*] res[a,b, , c , d,*,/,p,,c,m]) -- stack[] res[a,b, , c , d,*,/,p,,c,m,*,-]每一步按照上述原理进行就很容易理解如何将中缀式转为后缀式了。而转前缀式同理感兴趣的小伙伴可以自行去推导一下步骤~
