資訊專欄INFORMATION COLUMN
摘要：將表達式轉換為逆波蘭式，然后求值轉換中綴表達式為逆波蘭式魯棒性檢測，表達式中沒有操作數計算逆波蘭式值參考
表達式類算法題小結
[TOC]
聲明文章均為本人技術筆記，轉載請注明出處：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/
根據運算符與相關操作操作數的位置不同，將表達式分為前綴，中綴和后綴表達式；
前綴表達式(prefix)：又稱波蘭式(polish)，運算符位于相關操作數之前；
中綴表示式(infix)：運算符位于相關操作數之間，是通用的表達式記法；計算機計算中綴表達式，一般先將中綴表達式轉換為前綴或后綴表達式，然后再求值；
后綴表達式(postfix)：又稱逆波蘭式(reverse polish)，運算符位于相關操作數之后；逆波蘭式與前綴表達式是逆序關系；
lintcode：求逆波蘭（后綴）表達式值當一個表達式以逆波蘭式給出，無需考慮運算符優先級
假設給出逆波蘭式合法，從左到右挨個掃描逆波蘭式，
遇到數字，入棧；
遇到運算符，出棧相關操作數（加減乘除運算出棧2個操作數，自增自減出棧1個操作數）
加減乘除：第一個出棧元素為first, 第二個出棧元素為second，計算second op first，將計算結果入棧
自增自減：棧頂元素出棧，計算first++或first--，將計算結果入棧（阿里2017實習生算法題考點）；
假設給出逆波蘭式不保證合法，需檢查除法出棧的第一個元素是否為0，檢查遇到運算符時棧內元素數目是否滿足要求（阿里2017實習生算法題考點）；
復雜度分析：時間復雜度為$O(N)$，空間復雜度輔助棧占用空間為$O(N)$$；
/**
* 逆波蘭表達式 or 后綴表達式求值
* http://www.lintcode.com/en/problem/evaluate-reverse-polish-notation/
* @author yzwall
*/
class Solution {
public int evalRPN(String[] tokens) {
ArrayDeque stack = new ArrayDeque<>();
String Operations = "+-*/";
for (String token : tokens) {
if (!Operations.contains(token)) {
stack.push(Integer.parseInt(token));
continue;
}
int first = stack.pop();
int second = stack.pop();
if (token.equals("+")) {
stack.push(second + first);
} else if (token.equals("-")) {
stack.push(second - first);
} else if (token.equals("*")) {
stack.push(second * first);
} else {
stack.push(second / first);
}
}
return stack.pop();
}
}
lincode：將中綴表達式轉換為逆波蘭表達式
中綴表達式符合人類表達邏輯，運算符有優先級，除加減乘除運算外還有左右括號。用一個棧stack只負責存儲中綴表達式中的運算符號（右括號)不入棧）：
規定運算符優先級：規定加減運算優先級相等且最低，左右括號優先級相等且最高，乘除優先級相等介于中間；
轉換時從左往右掃描表達式，
空棧時，符號直接入棧；
棧不空時，
4.1 當前符號為右括號）：運算符棧一直出棧到逆波蘭式，直到棧頂為左括號(或者空棧；棧頂為左括號時，pop掉不加入逆波蘭式（bug點）；
4.2 當前符號為其他符號：優先級<=棧頂運算符優先級（bug點），運算符棧一直出棧到棧頂運算符優先級低于當前符號或者空棧；優先級>棧頂運算符優先級，直接入棧，
表達式掃描完畢后，如果棧不空將全部符號出棧到逆波蘭式；
復雜度分析時間復雜度為$O(N)$，空間復雜度輔助棧占用空間為$O(N)$
/**
* 將（中綴）表達式轉換為逆波蘭式（去掉括號）
* http://www.lintcode.com/zh-cn/problem/convert-expression-to-reverse-polish-notation/
* @author yzwall
*/
class Solution {
ArrayList convertToRPN(String[] expression) {
// 魯棒性檢測
ArrayList postfix = new ArrayList<>();
if (expression == null || expression.length == 0) {
return postfix;
}
// 規定運算符優先級
HashMap op = new HashMap<>();
op.put("+", 1);
op.put("-", 1);
op.put("*", 2);
op.put("/", 2);
op.put("(", 3);
op.put(")", 3);
// stack為運算符號棧
ArrayDeque stack = new ArrayDeque<>();
for (String token : expression) {
// 數字直接輸出到逆波蘭式
if (!op.containsKey(token)) {
postfix.add(token);
continue;
}
if (!stack.isEmpty()) {
// 遇到右括號，一直出棧（輸出到逆波蘭式）到棧頂為左括號或空棧
if (token.equals(")")) {
while (!stack.isEmpty()) {
if (stack.peek().equals("(")) {
stack.pop();
break;
}
postfix.add(stack.pop());
}
// 當前符號優先級低于棧頂符號，一直出棧到棧頂符號優先級低于當前符號或空棧
} else if (op.get(stack.peek()) >= op.get(token)) {
while (!stack.isEmpty() && op.get(stack.peek()) >= op.get(token)) {
// 左括號只有token為右空號時才出棧
if (stack.peek().equals("(")) {
break;
}
postfix.add(stack.pop());
}
stack.push(token);
} else { // 當前符號優先級高于棧頂符號，直接入棧
stack.push(token);
}
} else {
// 空棧，直接入棧
stack.push(token);
}
}
// 表達式掃描完畢，將棧內符號全部出棧到逆波蘭式
while (!stack.isEmpty()) {
postfix.add(stack.pop());
}
return postfix;
}
}
lintcode：求（中綴）表達式值
解題思路
將（中綴）表達式轉換為逆波蘭式；
求轉換后的逆波蘭式值；
注意：表達式中可能一個操作數都沒有，在進行2.之前進行魯棒性檢測，比如極端樣例
["(","(","(","(","(",")",")",")",")",")"]答案為0；
/**
* 給出（中綴）表達式，求表達值。將表達式轉換為逆波蘭式，然后求值
* http://www.lintcode.com/en/problem/expression-evaluation/
* @author yzwall
*/
class Solution {
public int evaluateExpression(String[] expression) {
int result = 0;
if (expression == null || expression.length == 0) {
return result;
}
// 1. 轉換（中綴）表達式為逆波蘭式
HashMap op = new HashMap<>();
ArrayList postfix = new ArrayList<>();
ArrayDeque stack = new ArrayDeque<>();
op.put("+", 1);
op.put("-", 1);
op.put("*", 2);
op.put("/", 2);
op.put("(", 3);
op.put(")", 3);
for (String token : expression) {
if (!op.containsKey(token)) {
postfix.add(token);
continue;
}
if (!stack.isEmpty()) {
if (token.equals(")")) {
while (!stack.isEmpty()) {
if (stack.peek().equals("(")) {
stack.pop();
break;
}
postfix.add(stack.pop());
}
} else if (op.get(stack.peek()) >= op.get(token)) {
while (!stack.isEmpty() && op.get(stack.peek()) >= op.get(token)) {
if (stack.peek().equals("(")) {
break;
}
postfix.add(stack.pop());
}
stack.push(token);
} else {
stack.push(token);
}
} else {
stack.push(token);
}
}
while (!stack.isEmpty()) {
postfix.add(stack.pop());
}
// 魯棒性檢測，表達式中沒有操作數
if (postfix.isEmpty()) {
return result;
}
// 2. 計算逆波蘭式值
ArrayDeque stack1 = new ArrayDeque<>();
for (String token : postfix) {
if (!op.containsKey(token)) {
stack1.push(Integer.parseInt(token));
continue;
}
int first = stack1.pop();
int second = stack1.pop();
if (token.equals("+")) {
stack1.push(second + first);
} else if (token.equals("-")) {
stack1.push(second - first);
} else if (token.equals("*")) {
stack1.push(second * first);
} else {
stack1.push(second / first);
}
}
result = stack1.pop();
return result;
}
}
參考
[1] http://blog.csdn.net/antineutrino/article/details/6763722/
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69965.html
摘要：攻擊中文名稱跨站請求偽造，也被稱為前端跨域問題及解決方案前端掘金同源策略同源策略限制從一個源加載的文檔或腳本如何與來自另一個源的資源進行交互。二叉搜索樹是二的數據結構與算法三集合前端掘金集合集合是由一組無序且唯一的項組成的。 你真的懂 JavaScript 的正則嗎？ - 掘金本文內容主要出處為《JavaScript權威指南》(第六版)，筆者只是在搬磚的同時整理思路，有誤望及時指出，感...
摘要：背景個人背景就讀于東北某普通二本院校計算機軟件工程專業，現大四，北京實習前端方向，自學，技術棧時間背景大概是在月日準備好簡歷開始投遞秋招差不多已經結束招聘崗位不多，投遞對象為大一些的互聯網公司事件背景第一個入職的是好未來的前端實習崗，待遇工 背景 個人背景 就讀于東北某普通二本院校計算機軟件工程專業，現大四，北京實習 前端方向，自學，vue技術棧 時間背景 大概是在11月9日準備...
摘要：背景個人背景就讀于東北某普通二本院校計算機軟件工程專業，現大四，北京實習前端方向，自學，技術棧時間背景大概是在月日準備好簡歷開始投遞秋招差不多已經結束招聘崗位不多，投遞對象為大一些的互聯網公司事件背景第一個入職的是好未來的前端實習崗，待遇工 背景 個人背景 就讀于東北某普通二本院校計算機軟件工程專業，現大四，北京實習 前端方向，自學，vue技術棧 時間背景 大概是在11月9日準備...
摘要：更多資源請文章轉自月份前端資源分享的作用數組元素隨機化排序算法實現學習筆記數組隨機排序個變態題解析上個變態題解析下中的數字前端開發筆記本過目不忘正則表達式聊一聊前端存儲那些事兒一鍵分享到各種寫給剛入門的前端工程師的前后端交互指南物聯網世界的 更多資源請Star：https://github.com/maidishike... 文章轉自：https://github.com/jsfr...
閱讀 1095·2021-11-15 18:00
閱讀 2808·2021-09-22 15:18
閱讀 1970·2021-09-04 16:45
閱讀 753·2019-08-30 15:55
閱讀 3865·2019-08-30 13:10
閱讀 1340·2019-08-30 11:06
閱讀 1988·2019-08-29 12:51
閱讀 2296·2019-08-26 13:55
