栈是一种限定仅在表尾进行插入和删除操作的线性表。栈的应用有很多，比如常见的递归，计算机表达式求值等。下面我们用栈来实现简易的四则运算计算器。
列一下本文的思路:
实现链栈的数据结构及其操作
中缀表达式转后缀表达式
后缀表达式求值
1、首先, 先实现一个链栈。
// 定义栈的数据结构
class Node
{
public $symbol;
public $next;
public function __construct($symbol, $next)
{
$this->symbol = $symbol;
$this->next = $next;
}
}
// 初始化栈, 生成头结点
function initStack(&$node)
{
$node = new Node(”, null);
}
// 入栈
function push(Node &$node, $symbol)
{
$p = new Node($symbol, null);
$p->next = $node->next;
$node->next = $p;
}
// 出栈
function pop(Node &$node, &$symbol)
{
if (null == $node->next) {
echo “ 栈空 \n”;
return;
}
$q = $node->next;
$symbol = $q->symbol;
$node->next = $node->next->next;
unset($q);
}
2、其次, 利用第一步实现的链栈，将中缀表达式转为后缀表达式。
// 获取运算符的优先级
function get_priority($symbol)
{
switch ($symbol) {
case ‘(‘:
$priority = 3;
break;
case ‘*’:
case ‘/’:
$priority = 2;
break;
case ‘+’:
case ‘-‘:
$priority = 1;
break;
case ‘)’:
$priority = 0;
break;
default:
$priority = 0;
break;
}
return $priority;
}
// 栈顶依次出栈, 如果遇到 '(‘ 则停止
function clear_stack(&$list)
{
$res = ”;
while (null != $list->next) {
if (‘(‘ != $list->next->symbol) {
pop($list, $item);
$res .= $item;
} else {
pop($list, $item);
return $res;
}
}
return $res;
}
// 中缀表达式转后缀表达式
function middle_to_back($middle_expression)
{
initStack($list);
$back_expression = ”;
$length = strlen($middle_expression);
for ($i = 0; $i < $length; $i ++) {
$symbol = $middle_expression[$i];
if (‘ ‘ != $symbol) {
if (is_numeric( $symbol) ) {// 数字直接输出
$back_expression .= $symbol;
} else {// 非数字则比较优先级
$stack_top_priority = get_priority(null == $list->next ? ” : $list->next->symbol);
$current_symbol_priority = get_priority($symbol);
if ($current_symbol_priority > $stack_top_priority) {// 优先级比栈顶高则进栈
push($list, $symbol);
} else {
$output = clear_stack($list);
$back_expression .= $output;
if (‘)’ != $symbol ) {
push($list, $symbol);
}
}
}
}
}
while (null != $list->next) {// 将栈清空
pop($list, $item);
$back_expression .= $item;
}
return $back_expression;
}
3、接下来, 我们利用第一步实现的链栈，和第二步得到的后缀表达式，计算最后的值。
// 是否是四则运算符号
function is_arithmetic_symbol($symbol)
{
$arithmetic_symbols = array(‘+’, ‘-‘, ‘*’, ‘/’);
if (in_array( $symbol, $arithmetic_symbols) ) {
return true;
} else {
return false;
}
}
// 计算后缀表达式的值
function calculate($expression)
{
$stack = new Node(”, null);
$length = strlen($expression);
for ($i = 0; $i < $length; $i ++) {
if (‘ ‘ != $expression[ $i] ) {// 为空则跳过
if (is_numeric( $expression[ $i] ) ) {
push($stack, $expression[ $i] );
} else if (is_arithmetic_symbol( $expression[ $i] ) ) {
pop($stack, $n1);
pop($stack, $n2);
$res = get_result($n2, $n1, $expression[ $i] );
push($stack, $res);
} else {
echo “wrong symbol, exit”;
exit();
}
}
}
$value = $stack->next->symbol;
return $value;
}
最后，我们测试一下所实现的计算器。
function main()
{
$back_expression = middle_to_back(‘((1+2)*3-4) * 5’ );
$result = calculate($back_expression);
echo “ 后缀表达式的值为: ” . $back_expression, PHP_EOL;
echo “result : ” . $result, PHP_EOL;
}
main();
得到的结果如下:
简易的计算器就实现啦！~~~（代码中有一些细节未做判断，希望读者理解。欢迎大家提出批评修改意见，感谢~）