bash shell数组模拟栈求四则运算混合表达式(逆波兰式)

原帖：http://blog.csdn.net/sosodream/article/details/5645684

我稍微多谢了一些注释，方便理解。

#!/bin/bash

########################################################## 

#需求：四则运算混合表达式求值 

#描述： 

#       采用shell实现基于简单的加减乘除的混合表达式求值 

#分析： 

#   0:简单的加减乘除(a b;a-b;a*b;a/b)直接调用工具计算 

#   a:算法：先求出逆波兰表达式，然后计算逆波兰表达式 

#   b:数据结构：采用数组保存（用数组模拟栈） 

#脚本说明： 

#脚本调用: 

#       sh rpn.sh /( 2 /* /( 2 4 /) /( 2 4 /* 2 /) /) // 11 

#脚本参数: 

#       表达式(字符数字， -*/和括号),按空格分开, 

#       “括号”和“*”要注意shell转义 

#脚本输出： 

#       第一行：逆波兰表达式(空格分离) 

#       第二行：表达式计算值 

########################################################## 

declare -a stack_rpn  #全局变量，保存逆波兰表达式 

scale=3; #精度 

 

 

#1.0数组公函区 

#用数组模拟栈 

##将$2加入到数组$1的末尾形成新的$1,类是于压栈

array_push() 

{ 

        local arrayname=$1 

        local newitem=$2 

        #"use to avoid '*' transfer 

        eval ${arrayname}'=("${'${arrayname}'[@]}" "$newitem" ) '  

} 

##从数组$1的第一个元素位置取（总元素个数减一）个元素并重新赋值到$1中，即去掉数组最后一个元   ##素，类似于出栈，将栈顶元素抛弃                                                             array_pop() 

{ 

        local arrayname=$1 

        eval ${arrayname}'=("${'${arrayname}'[@]:0:$((${#'${arrayname}'[@]}-1))}") ' 

} 

##输出数组最后一个元素，类似于输出栈顶元素                                                  array_top()                       

{ 

        local arrayname=$1 

        eval echo '"${'${arrayname}'[$((${#'${arrayname}'[@]}-1))]}"' 

}  

## 删除数组$1的第一个参数，即数组参数向左移动一个单位                                          array_shift() 

{ 

        local arrayname=$1 

        eval ${arrayname}'=( "${'${arrayname}'[@]:1}" )'          

} 

##取栈底元素，即是取数组

array_bt() 

{ 

        local arrayname=$1 

        eval echo '"${'${arrayname}'[0]}"' 

} 

 

#判断数组索引是否存在 

#起始索引是1 

array_has_index() 

{ 

        local arrayname=$1 

        local index=${2-1} 

        local max 

 

        eval max='${#'${arrayname}'[*]}' 

 

        eval test "$index" -ge 1 -a  "$index" -le "$max"  2>/dev/null 

        echo $? 

} 

 

#中缀表达式切换成逆波兰表达式 

#参数：中缀表达式(空格分隔，注意*号转义） 

#输出：逆波兰表达式 

mkrpn() 

{ 

        local item; 

        local -a result; 

        local -a temp; 

        local i; 

 

        array_push temp "#"; 

 

        while [ $# -ne 0 ] 

        do 

                item=$1; 

                case "$item" in  

                " "|"-") 

                        while [ "$(array_top temp)" != '(' ] && [ "$(array_top temp)" != '#' ] 

                        do 

                                i=$(array_top temp); 

                                array_pop temp ; 

                                array_push result "$i"; 

                        done  

 

                        array_push temp "$item"; 

                ;; 

                "*"|"/") 

                # a/b*c*(d e) : a b / c * d e * 

                        while [ "$(array_top temp)" = '*' ] || [ "$(array_top temp)" = '/' ] 

                        #while test "$(array_top temp)" = "*" -o "$(array_top temp)" = "/"  

                        do 

                                i="$(array_top temp)"; 

                                array_pop temp ; 

                                array_push result "$i"; 

                        done 

 

                        array_push temp "$item"; 

                ;; 

                ")") 

                        while test "$(array_top temp)" != "(" 

                        do 

                                i="$(array_top temp)"; 

                                array_pop temp ; 

                                array_push result "$i"; 

 

                        done 

 

                        array_pop temp ; 

                ;; 

                "(") 

                        array_push temp "$item"; 

                ;; 

                *) 

                #数字 

                        array_push result "$item"; 

                ;; 

                esac 

 

                shift 

        done 

 

        while test "$(array_top temp)" != "#" 

        do 

                i="$(array_top temp)"; 

                array_pop temp ; 

                array_push result "$i"; 

        done 

 

        echo "${result[@]}" 

 

        stack_rpn=( "${result[@]}" ); 

} 

 

 

#计算逆波兰表达式 

#输入：逆波兰表达式，保存于全局数组stack_rpn 

#输出:表达式值 

calrpn() 

{ 

        local -a dig_stack 

        local i; 

        local op1; 

        local op2; 

        local result; 

 

        while test "$(array_has_index stack_rpn)" -ne 1  

        do 

 

                i=$stack_rpn; 

                array_shift stack_rpn ;  

                case "$i" in 

                " "|"-"|"*"|"/") 

                        op1=$(array_top dig_stack); 

                        array_pop dig_stack ; 

                        op2=$(array_top dig_stack); 

                        array_pop dig_stack ; 

                        result=$(echo "scale=$scale;$op2 $i $op1 "|bc); 

                        array_push dig_stack "$result"; 

                ;; 

                *) 

                        array_push dig_stack "$i"; 

                ;; 

                esac 

        done 

        array_top dig_stack; 

} 

 

#main 

mkrpn "$@" 

calrpn