资讯专栏INFORMATION COLUMN

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

solocoder / 1417人阅读

摘要:下面我们用栈来实现简易的四则运算计算器。列一下本文的思路实现链栈的数据结构及其操作中缀表达式转后缀表达式后缀表达式求值首先先实现一个链栈。是否是四则运算符号计算后缀表达式的值为空则跳过最后,我们测试一下所实现的计算器。

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

列一下本文的思路:

实现链栈的数据结构及其操作

中缀表达式转后缀表达式

后缀表达式求值

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 "栈空
";

        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();

得到的结果如下:

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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/29988.html

相关文章

  • #yyds干货盘点# PTA数据结构(C++)——7-1 队列的实现及基本操作(链栈实现,无上限)

    摘要:队列的元素值均为整数。输入格式输入第行为个正整数,表示操作个数接下来行,每行表示一个操作,格式为或。表示将整数入队,表示出队。若某出队操作不合法如在队列空时出队,则对该操作输出。 1.编译运行2.题目:给定一个初始为空的队列和一系列入队、出队操作,请编写程序输出每次出队的元素。队列的元素值均为整数。输入格式:输...

    zlyBear 评论0 收藏0
  • JAVA HashMap

    摘要:采用链地址法来处理冲突这个就被赋值到里面去了。的应用非常广泛,是新框架中用来代替的类,也就是说建议使用,不要使用的方法是同步的,未经同步直接使用对象的中数组默认大小是,增加的方式是。中数组的默认大小是,而且一定是的指数 Hashmap采用链地址法来处理冲突: void addEntry(int hash, K key, V value, int bucketIndex) { ...

    vspiders 评论0 收藏0
  • 【数据结构】栈的实现——顺序栈和链栈

    摘要:一栈的定义定义限定只在表的一端表尾进行插入和删除的线性表特点后进先出二顺序栈基于数组实现实现代码头文件栈的最大存储定义一个顺序栈类使用模板使用模板优点可以用来实现多种数据类型的存储数据域栈的大小栈顶 ...

    RyanQ 评论0 收藏0
  • 算法学习之数据结构线性表、堆、栈

    摘要:栈底是固定的,而栈顶浮动的如果栈中元素个数为零则被称为空栈。入栈将数据保存到栈顶。链栈链栈是指栈的链式存储结构,是没有附加头节点的运算受限的单链表,栈顶指针是链表的头指针。 一、喜欢单挑线性表 1.线性表的特性 线性表是一个线性结构,它是一个含有n≥0个节点的有限序列。在节点中,有且仅有一个开始节点没有前驱并有一个后继节点,有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且...

    huaixiaoz 评论0 收藏0
  • 乐字节-Java8新特性-接口默认方法

    摘要:注意当多个父接口中存在相同的默认方法时,子类中以就近原则继承。定义静态默认方法这是版简易计算器接口默认方法使用定义接口并提供默认打印方法定义接口默认方法支持方法形参这是数值运算基本接口。。。 总概 JAVA8 已经发布很久,而且毫无疑问,java8是自java5(2004年发布)之后的最重要的版本。其中包括语言、编译器、库、工具和JVM等诸多方面的新特性。 Java8 新特性列表如下:...

    arashicage 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<