用链栈实现简易四则运算计算器(php版)

栈是一种限定仅在表尾进行插入和删除操作的线性表。栈的应用有很多，比如常见的递归，计算机表达式求值等。下面我们用栈来实现简易的四则运算计算器。
列一下本文的思路:

实现链栈的数据结构及其操作
中缀表达式转后缀表达式
后缀表达式求值

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();
得到的结果如下:

简易的计算器就实现啦！~~~（代码中有一些细节未做判断，希望读者理解。欢迎大家提出批评修改意见，感谢~）