栈的数据结构完成表达式(5*10+2-7+5)/10+5的计算

这篇具有很好参考价值的文章主要介绍了栈的数据结构完成表达式(5*10+2-7+5)/10+5的计算。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

栈的数据结构完成表达式(5*10+2-7+5)/10+5的计算

栈(Stack)是一种线性数据结构,具有后进先出(LIFO)的特性。它可以理解为一种类似于抽屉的容器,只能在顶部进行插入和删除操作,其他位置不可访问。栈的基本操作包括入栈(push)和出栈(pop),其中入栈将元素放入栈顶,出栈将栈顶元素移出。

栈在计算机科学和软件开发中有广泛的应用场景,以下是一些常见的使用场景:

1. 表达式求值:栈可以用于解析和计算数学表达式,如中缀表达式转换为后缀表达式,并利用栈进行后缀表达式的求值。

2. 函数调用:在程序执行过程中,每次函数调用时会将当前函数的上下文保存到栈中,包括局部变量、返回地址等。当函数执行完毕后,从栈中取出上一个函数的上下文并恢复执行。

3. 浏览器的历史记录:浏览器通过栈结构来管理用户访问页面的历史记录。每次用户访问一个新页面时,将该页面的 URL 压入栈中;当用户点击返回按钮时,从栈中弹出最近访问的页面 URL,以便回退到上一个页面。

4. 撤销操作:许多应用程序支持撤销操作,其中栈被用于存储每个操作的状态或内容。当用户选择撤销操作时,可以从栈中逐步恢复先前的状态。

5. 地址转跳:在汇编语言和操作系统设计中,栈被用于存储函数调用期间的返回地址。这使得函数可以通过将返回地址压入栈中并使用跳转指令来返回到调用者。

6. 括号匹配:栈可以用于检查表达式中的括号是否匹配。遍历表达式,当遇到左括号时将其压入栈中,当遇到右括号时,若栈顶元素为匹配的左括号,则将栈顶元素弹出,否则说明括号不匹配。

总之,栈是一个非常有用的数据结构,在许多算法和程序设计的场景中都发挥着重要作用,它提供了一种便捷的方式来实现后进先出的操作。

python源码实现

以下是一个使用栈完成表达式计算的示例代码:

class Stack:
    def __init__(self):
        self.stack = []

    def is_empty(self):
        return len(self.stack) == 0

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("Stack is empty")

    def top(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("Stack is empty")

def calculate_expression(expression):
    # 定义操作符优先级
    priority = {'+': 1, '-': 1, '*': 2, '/': 2}

    def apply_operator(operator_stack, operand_stack):
        operator = operator_stack.pop()
        operand2 = operand_stack.pop()
        operand1 = operand_stack.pop()

        if operator == '+':
            result = operand1 + operand2
        elif operator == '-':
            result = operand1 - operand2
        elif operator == '*':
            result = operand1 * operand2
        elif operator == '/':
            result = operand1 / operand2
        else:
            raise ValueError("Invalid operator")

        operand_stack.push(result)

    def evaluate(expression):
        operator_stack = Stack()
        operand_stack = Stack()

        for char in expression:
            if char.isdigit():
                operand_stack.push(int(char))
            elif char in priority:
                while (not operator_stack.is_empty() and
                       priority[char] <= priority[operator_stack.top()]):
                    apply_operator(operator_stack, operand_stack)
                operator_stack.push(char)
            elif char == '(':
                operator_stack.push(char)
            elif char == ')':
                while (not operator_stack.is_empty() and
                       operator_stack.top() != '('):
                    apply_operator(operator_stack, operand_stack)
                if operator_stack.is_empty():
                    raise ValueError("Invalid expression")
                operator_stack.pop()

        while not operator_stack.is_empty():
            apply_operator(operator_stack, operand_stack)

        return operand_stack.top()

    return evaluate(expression)

# 测试表达式计算
expression = "(5*10+2-7+5)/10+5"
result = calculate_expression(expression)
print(f"Expression: {expression}")
print(f"Result: {result}")

运行以上代码,将会输出以下结果:

Expression: (5*10+2-7+5)/10+5
Result: 8.5

这段代码使用栈来模拟了表达式的计算过程。首先遍历表达式中的字符,如果是数字,则直接将其放入操作数栈;如果是操作符,则与操作符栈顶的操作符进行比较优先级,如果当前操作符的优先级小于等于栈顶操作符的优先级,则执行栈顶操作符与操作数的计算,并将结果放回操作数栈,直到优先级满足要求。遇到括号时,需要特殊处理。最后,当表达式遍历完毕后,计算剩余的操作符和操作数得到最终结果。

Java源码实现

import java.util.Stack;

public class ExpressionCalculator {
    public static double calculateExpression(String expression) {
        Stack<Double> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            if (ch == ' ') {
                continue; // 跳过空格
            }

            if (Character.isDigit(ch)) {
                StringBuilder num = new StringBuilder();
                while (i < expression.length() && (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
                    num.append(expression.charAt(i++));
                }
                operandStack.push(Double.parseDouble(num.toString()));
                i--; // 回退一位,因为在for循环中会自增
            } else if (ch == '(') {
                operatorStack.push(ch);
            } else if (ch == ')') {
                while (operatorStack.peek() != '(') {
                    performOperation(operandStack, operatorStack);
                }
                operatorStack.pop(); // 弹出左括号
            } else if (isOperator(ch)) {
                while (!operatorStack.isEmpty() && hasHigherPrecedence(ch, operatorStack.peek())) {
                    performOperation(operandStack, operatorStack);
                }
                operatorStack.push(ch);
            }
        }

        while (!operatorStack.isEmpty()) {
            performOperation(operandStack, operatorStack);
        }

        return operandStack.pop();
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    private static boolean hasHigherPrecedence(char op1, char op2) {
        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
            return true;
        }
        return false;
    }

    private static void performOperation(Stack<Double> operandStack, Stack<Character> operatorStack) {
        double num2 = operandStack.pop();
        double num1 = operandStack.pop();
        char operator = operatorStack.pop();

        double result = 0;
        switch (operator) {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num1 - num2;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num1 / num2;
                break;
        }

        operandStack.push(result);
    }

    public static void main(String[] args) {
        String expression = "(5 * 10 + 2 - 7 + 5) / 10 + 5";
        double result = calculateExpression(expression);
        System.out.println("Result: " + result);
    }
}

具体实现过程如下:

  1. 定义两个栈,一个用于存储操作数(operandStack),另一个用于存储运算符(operatorStack)。

  2. 遍历输入的表达式字符串中的每个字符,根据字符的不同类型执行不同的操作:

    • 如果是数字,将其转换为整数并压入操作数栈中;

    • 如果是左括号,将其压入运算符栈中;

    • 如果是右括号,从运算符栈中弹出所有左括号,直到遇到左括号为止,然后对操作数栈中的元素进行计算,并将结果压入操作数栈中;

    • 如果是运算符,从运算符栈中弹出一个运算符,如果该运算符的优先级高于当前运算符,则先对操作数栈中的元素进行计算,然后再进行当前运算符的计算;否则直接进行当前运算符的计算。最后将计算结果压入操作数栈中。

  3. 当运算符栈为空时,说明已经完成了所有的计算,此时从操作数栈中取出最后一个元素作为最终的结果。

  4. 在主函数中调用calculateExpression方法,传入一个表达式字符串作为参数,并输出计算结果。文章来源地址https://www.toymoban.com/news/detail-483319.html

到了这里,关于栈的数据结构完成表达式(5*10+2-7+5)/10+5的计算的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式,是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式,可以表示为 那么问题就来了,树只是一种抽象的数据

    2024年02月08日
    浏览(47)
  • 《数据结构》:中缀表达式转后缀表达式 + 后缀表达式的计算

    补充了一个判断输入中缀表达式 合法性 的代码: 《数据结构》:中缀表达式合法性判断_Amentos的博客-CSDN博客   目录 一、基本概念 二、中缀表达式转后缀表达式    例       中缀表达式  2*(3+5)+7/1-4  转换为后缀表达式 三、后缀表达式的计算    例       后缀表达式

    2024年02月03日
    浏览(67)
  • 【数据结构】13:表达式转换(中缀表达式转成后缀表达式)

    从头到尾依次读取中缀表达式里的每个对象,对不同对象按照不同的情况处理。 如果遇到空格,跳过 如果遇到运算数字,直接输出 如果遇到左括号,压栈 如果遇到右括号,表示括号里的中缀表达式已经扫描完毕,将栈顶的运算符弹出并输出, 直至遇到左括号(左括号出栈

    2024年02月19日
    浏览(52)
  • 【数据结构】超详细讲解:算术表达式转化为后缀表达式、前缀表达式、表达式树的构建

    作者: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: 【数据结构】:该专栏专注于数据结构知识,持续更新,每一篇内容优质,浅显易懂,不失深度! 近期目标: 写好专栏

    2024年02月08日
    浏览(53)
  • C++ 数据结构 栈 中缀表达式转后缀表达式并求值

    写在前面,这里用的是我自己写的Stack类,并非STL,实现方法为静态数组,但使用过程中的函数方法一样,无伤大雅。(完整code和Stack_static类赋在最后) 1.从左到右遍历 2.数,即参与运算数,直接放进后缀表达式之后 3.左括号 ,直接压入栈(因为括号的优先级最高,无需判断

    2024年02月03日
    浏览(49)
  • 数据结构之表达式求值

     前言 运用堆栈解决表达式的求值,代码思路为: 1.定义两个栈,一个char类型的栈用于存放运算符(ysf)一个int类型的栈用于存放操作数(czs) 如一个表达式3+6*9,将“+”,“*”入ysf栈,将“3”“6”“9”入czs栈 2.运用getchar进行数据的录入,如果接收的是运算符,将其插入到运

    2024年04月29日
    浏览(35)
  • 数据结构 实验2——表达式求值

    一、实验名称:表达式求值 二、实验学时: 6 学时 三、实验目的 1.理解栈的结构特点和基本操作特性; 2.掌握利用栈实现表达式求值算法。 四、实验内容 ( 步骤 ) 输入一个算术表达式(以“=”结束),求其值。要求表达式以“=”结束,操作数为多位实数,对错误表达式要进行

    2023年04月08日
    浏览(39)
  • 数据结构 | 后缀表达式【深入剖析堆栈原理】

    Hello,大家好,国庆的第二天,带来的是数据结构中堆栈部分的后缀表达式,这也是一块有关栈的应用方面困扰了众多同学的一个大难题,今天就让我们一起解决这个难题📕 后缀表达式也称为 逆波兰表达式 ,也就是将算术运算符放在操作数的后面 例如【1 + 2 * 3】的后缀表达

    2023年04月27日
    浏览(48)
  • 【数据结构】12 堆栈应用:表达式求值

    有一个常量表达式的中缀表达式为:5 + 6 / 2 - 3 * 4,其后缀形式表示为: 5 6 2 / + 3 4 × -。后缀表达式的特点是运算符位于两个预算数之后。其前缀表达式为: - + 5 / 6 2 × 3 4。 后缀表达式相比于中缀表达式的求值要容易很多。 从左到右扫描该表达式: (1)遇见运算数5 6 2时不

    2024年02月20日
    浏览(59)
  • 【数据结构】反射、枚举以及lambda表达式

    Java的反射(reflection)机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任 意一个对象,都能够调用它的任意方法和属性,既然能拿到那么,我们就可以修改部分类型信息;这种动态获取信 息以及动态调用对象方法的功能称为java语言的反射

    2024年03月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包