1.0 問題描述
實(shí)現(xiàn)10以內(nèi)四則運(yùn)算（只包含數(shù)字，+-*/和小括號）
2.0 問題分析
- 四則運(yùn)算使用“后綴表達(dá)式”算法來計(jì)算，后綴表達(dá)式可以無需考慮運(yùn)算符優(yōu)先級溃槐，直接從左至右依次計(jì)算对人。
- 問題分解成2部分，一是將“中綴表達(dá)式”（我們正常寫的四則運(yùn)算字符串樣式，即我們的輸入表達(dá)式）轉(zhuǎn)為“后綴表達(dá)式”；二是使用“后綴表達(dá)式”求值。
- “中綴表達(dá)式”轉(zhuǎn)“后綴表達(dá)式”流程：
- 首先建立一個(gè)棧和一個(gè)隊(duì)列，分別為“符號椡捅模”和“結(jié)果隊(duì)列”：“符號椑樱”用于保存符號，處理符號優(yōu)先級；“結(jié)果隊(duì)列”用于保存“后綴表達(dá)式”
- 依次遍歷“中綴表達(dá)式”的字符毫玖。
- 若是數(shù)字直接進(jìn)結(jié)果隊(duì)列。
- 若是運(yùn)算符凌盯，則需查看符號棧頂元素付枫。
- 如果棧為空或棧頂元素為“(”則直接進(jìn)符號棧。
- 否則驰怎，需要將符號棧頂部所有優(yōu)先級低于當(dāng)前運(yùn)算符的所有符號依次出棧励背，進(jìn)入結(jié)果隊(duì)列。
- 若是“)”砸西，重復(fù)彈出棧頂運(yùn)算符叶眉，進(jìn)入結(jié)果隊(duì)列，直到遇到“(”芹枷，將其丟棄衅疙。
- 遍歷完成后，即生成了“后綴表達(dá)式”鸳慈，求值過程如下：
- 創(chuàng)建一個(gè)“數(shù)字棻ヒ纾”，用于保存計(jì)算結(jié)果走芋。
- 結(jié)果隊(duì)列依次出隊(duì)列绩郎。
- 若是數(shù)字直接進(jìn)“數(shù)字棧”翁逞。
- 若是運(yùn)算符肋杖，則從“數(shù)字棧”彈出2個(gè)數(shù)值挖函，與此運(yùn)算符計(jì)算后状植，再進(jìn)“數(shù)字棧”怨喘。
- 重復(fù)上面的過程津畸，直到“數(shù)字棧”剩余1個(gè)數(shù)字必怜。這個(gè)數(shù)字即為計(jì)算結(jié)果肉拓。
3.0 代碼實(shí)現(xiàn)
3.1使用swift實(shí)現(xiàn)
/**
* 把Character轉(zhuǎn)換成Doublec
* @param {Character} c - 需要轉(zhuǎn)換的字符
* @return {Double} 返回c對應(yīng)的數(shù)字
*/
func _c2n(_ c: Character) throws -> Double{
guard case "0" ... "9" = c else {
throw AlgorithmError.msg("符號范圍錯(cuò)誤");
}
let zero = "0".unicodeScalars.first!.value;
return Double(c.unicodeScalars.first!.value - zero);
}
/**
* 最小單元計(jì)算 {n1}{mark}{n2}
* @param {Double} n1 - 數(shù)字1
* @param {Double} n2 - 數(shù)字2
* @param {Character} mark - 符號
* @return {Double} 返回 {n1}{mark}{n2} 的結(jié)果
*/
func _eval(_ n1: Double, _ n2: Double, _ mark: Character) throws -> Double{
switch mark {
case "+":
return n1 + n2;
case "-":
return n1 - n2;
case "*":
return n1 * n2;
case "/":
if n2 == 0 {
throw AlgorithmError.msg("除0錯(cuò)誤");
}
return n1 / n2;
default:
throw AlgorithmError.msg("符號錯(cuò)誤");
}
}
/**
* 比較符號
* @param {String} a - 符號a
* @param {String} b - 符號b
* @return {Bool} 如果a的優(yōu)先級<=b的優(yōu)先級返回true，否則返回false
*/
func _arithmeticCompare(_ a: Character, _ b: Character) throws -> Bool {
switch b {
case "+", "-":
return a == "+" || a == "-";
case "*", "/":
return true;
case "(":
return false;
default:
throw AlgorithmError.msg("非法符號");
}
}
/**
* 計(jì)算10以內(nèi)的四則運(yùn)算
* @param {String} str - 輸入中綴表達(dá)式
* @return {Double} - 返回計(jì)算結(jié)果
*/
func arithmetic(_ str: String) throws -> Double{
//結(jié)果棧
let retStack = Stack<Character>();
//符號棧
let markStack = Stack<Character>();
var lastC: Character? = nil;
for c in str{
switch c{
case "(":
if let lc = lastC, case "0"..."9" = lc{
throw AlgorithmError.msg("發(fā)現(xiàn)錯(cuò)誤");
}
//直接進(jìn)符號
markStack.push(c);
break
case ")":
//依次出棧直到括號結(jié)束
while markStack.top() != "(" && markStack.count() > 0 {
if let m = markStack.pop(){
retStack.push(m);
}
}
if markStack.count() > 0 {
markStack.pop();
}else{
throw AlgorithmError.msg("發(fā)現(xiàn)錯(cuò)誤");
}
break
case "+", "-", "*", "/":
//比c優(yōu)先級高的都進(jìn)結(jié)果棧
if let t = markStack.top(){
while true {
if let c = try? _arithmeticCompare(c, t), c{
markStack.pop();
retStack.push(t);
if markStack.count() == 0{
break;
}
}else{
break;
}
}
}
markStack.push(c);
break;
case "0"..."9":
if let lc = lastC , case "0"..."9" = lc {
throw AlgorithmError.msg("發(fā)現(xiàn)錯(cuò)誤");
}
//直接進(jìn)結(jié)果
retStack.push(c);
break;
default:
throw AlgorithmError.msg("發(fā)現(xiàn)錯(cuò)誤");
}
lastC = c;
}
//符號検崆欤可能不空
while markStack.count() > 0 {
retStack.push(markStack.pop()!);
}
//計(jì)算結(jié)果
let numStack = Stack<Double>();
while retStack.count() > 0 {
if let c = retStack.shift(){
if case "0"..."9" = c {//數(shù)字
numStack.push(try _c2n(c));
}else{//符號
if numStack.count() >= 2{
if let n1 = numStack.pop(), let n2 = numStack.pop() {
numStack.push(try _eval(n2, n1, c));
}
}else{
throw AlgorithmError.msg("發(fā)現(xiàn)錯(cuò)誤");
}
}
}
}
if numStack.count() != 1{
throw AlgorithmError.msg("發(fā)現(xiàn)錯(cuò)誤");
}
return numStack.pop()!;
}
3.2使用js實(shí)現(xiàn)
function size(inputArr){
let stack1 = [];
let stack2 = [];
let validMark = (m) => {
return ['+', '-', '*', '/', '(', ')'].includes(m);
}
let compareDict = {
'+': 0,
'-': 0,
'*': 1,
'/': 1
}
let compare = (a, b) => {
if(!compareDict.hasOwnProperty(a) || !compareDict.hasOwnProperty(b)){
throw `錯(cuò)誤符號 a=${a} b=$暖途`;
}
return compareDict[a] < compareDict[b];
}
//中綴轉(zhuǎn)后綴
//數(shù)字直接入棧2卑惜，符號如果優(yōu)先級低于棧頂，依次出棧1丧肴，入棧2.
for (const e of inputArr) {
let num = Number.parseInt(e);
//數(shù)字直接入棧2
if(!Number.isNaN(num)){
stack2.push(num);
}else{//非數(shù)字残揉，2種情況胧后，可能是括號芋浮，可能是非括號
if(!validMark(e)){
throw `非法符號${e}`;
}
if(e == '('){//左括號直接入棧1
stack1.push(e);
}else if(e == ')'){//右括號依次出棧
let mark = null;
let valid = false;
while(stack1.length > 0 && mark != '('){//復(fù)雜度O(1)
mark = stack1.pop();
if(mark != '('){
stack2.push(mark);
}else{
valid = true;
}
}
if(!valid){
throw '非法表達(dá)式';
}
}else{//如果是正常運(yùn)算符，則依次與棧1頂元素比較壳快，若棧頂元素優(yōu)先級高纸巷，則出棧
let mark = null;
let handled = false;
while(stack1.length > 0 && mark != '('){//復(fù)雜度O(1)
mark = stack1.pop();
//只有棧頂元素優(yōu)先級 < e時(shí)才結(jié)束循環(huán)，否則棧頂元素優(yōu)先級 >= e時(shí)眶痰，就不停出棧
if(mark == '(' || compare(mark, e)){
stack1.push(mark);
stack1.push(e);
handled = true;
break;
}else{
stack2.push(mark);
}
}
//所有符號都出棧了或者遇到了'('
if(!handled){
stack1.push(e);
}
}
}
}
while(stack1.length > 0){
stack2.push(stack1.pop());
}
if(stack1.length != 0){
throw '表達(dá)式錯(cuò)誤';
}
while(stack2.length > 0){//O(n)
let mark = stack2.shift();
let num = Number.parseInt(mark);
if(!Number.isNaN(num)){//數(shù)字
stack1.push(num);
}else{//符號
let n1 = stack1.pop();
let n2 = stack1.pop();
if(!n1 || !n2){
throw '表達(dá)式錯(cuò)誤';
}
let v = eval(`${n2}${mark}${n1}`);
stack1.push(v);
}
}
console.log(`stack1=${stack1}`);
return stack1.pop();
}
4.0 復(fù)雜度分析
上述2個(gè)過程復(fù)雜度都比較低瘤旨，如果遇到數(shù)字都是直接保存，遇到符號會(huì)進(jìn)行一次比較或計(jì)算竖伯，時(shí)間復(fù)雜度為O(n)存哲。
上述算法中使用了3個(gè)棧或隊(duì)列七婴，其中2個(gè)棧能夠重復(fù)使用祟偷，空間復(fù)雜度為O(2n)。
5.0 注意
上面的算法只是關(guān)注算法本身邏輯打厘，健壯性及通用性比較差修肠，如果用于正式的程序，還需要增加很多驗(yàn)證邏輯及更多運(yùn)算符的支持户盯。
