数据结构中栈的算术表达式求值

栈在算术表达式求值中起到了重要的作用。栈可以用来保存运算符和操作数，并按照一定的规则进行出栈和入栈操作，最终得到表达式的计算结果。

算术表达式求值的基本思路是通过扫描表达式，遇到操作数就入栈，遇到运算符就与栈顶运算符进行比较，如果当前运算符优先级较高，则入栈，否则将栈顶运算符出栈并进行计算，将计算结果再次入栈。重复这个过程直到表达式扫描完毕。

以下是栈在算术表达式求值中的具体步骤：
1. 创建一个空栈用于保存运算符和操作数。
2. 从左到右扫描表达式的每个字符。
3. 如果遇到操作数，则将其转换为数字并入栈。
4. 如果遇到运算符，则与栈顶运算符进行比较：
- 如果当前运算符优先级较高，则入栈。
- 如果当前运算符优先级较低或相等，则将栈顶运算符出栈并进行计算，将计算结果再次入栈。
5. 当表达式扫描完毕后，依次将栈中剩余的运算符出栈并进行计算，直到栈为空。
6. 最终栈中剩余的唯一元素即为表达式的计算结果。

相关问题

数据结构栈的算术表达式求值C语言

栈是一种后进先出（LIFO）的数据结构，它可以用来解决算术表达式求值问题。下面是一个使用栈求解算术表达式的C语言程序：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_STACK_SIZE 100

typedef struct {
    int top;
    int data[MAX_STACK_SIZE];
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int is_empty(Stack *s) {
    return s->top == -1;
}

int is_full(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

void push(Stack *s, int x) {
    if (is_full(s)) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->data[++s->top] = x;
}

int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top--];
}

int peek(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top];
}

int evaluate(char *expr) {
    Stack operand_stack;
    Stack operator_stack;
    init(&operand_stack);
    init(&operator_stack);

    while (*expr != '\0') {
        if (isdigit(*expr)) {
            int value = 0;
            while (isdigit(*expr)) {
                value = value * 10 + (*expr - '0');
                expr++;
            }
            push(&operand_stack, value);
        } else if (*expr == '(') {
            push(&operator_stack, *expr);
            expr++;
        } else if (*expr == ')') {
            while (peek(&operator_stack) != '(') {
                int op2 = pop(&operand_stack);
                int op1 = pop(&operand_stack);
                char op = pop(&operator_stack);
                int result;
                switch (op) {
                    case '+': result = op1 + op2; break;
                    case '-': result = op1 - op2; break;
                    case '*': result = op1 * op2; break;
                    case '/': result = op1 / op2; break;
                }
                push(&operand_stack, result);
            }
            pop(&operator_stack);
            expr++;
        } else if (*expr == '+' || *expr == '-' || *expr == '*' || *expr == '/') {
            while (!is_empty(&operator_stack) && peek(&operator_stack) != '(' && ((*expr == '+' || *expr == '-') && (peek(&operator_stack) == '*' || peek(&operator_stack) == '/'))) {
                int op2 = pop(&operand_stack);
                int op1 = pop(&operand_stack);
                char op = pop(&operator_stack);
                int result;
                switch (op) {
                    case '+': result = op1 + op2; break;
                    case '-': result = op1 - op2; break;
                    case '*': result = op1 * op2; break;
                    case '/': result = op1 / op2; break;
                }
                push(&operand_stack, result);
            }
            push(&operator_stack, *expr);
            expr++;
        } else {
            printf("Invalid character: %c\n", *expr);
            exit(1);
        }
    }

    while (!is_empty(&operator_stack)) {
        int op2 = pop(&operand_stack);
        int op1 = pop(&operand_stack);
        char op = pop(&operator_stack);
        int result;
        switch (op) {
            case '+': result = op1 + op2; break;
            case '-': result = op1 - op2; break;
            case '*': result = op1 * op2; break;
            case '/': result = op1 / op2; break;
        }
        push(&operand_stack, result);
    }

    return pop(&operand_stack);
}

int main() {
    char expr[100];
    printf("Enter an arithmetic expression: ");
    scanf("%s", expr);
    int result = evaluate(expr);
    printf("Result: %d\n", result);
    return 0;
}

该程序使用两个栈，一个用于存储操作数，另一个用于存储运算符。它遍历算术表达式中的每个字符，并根据字符的类型执行相应的操作。如果字符是数字，则将其转换为整数并将其推入操作数栈中；如果字符是左括号，则将其推入运算符栈中；如果字符是右括号，则从运算符栈中弹出运算符和操作数，执行相应的运算，并将结果推入操作数栈中，直到遇到左括号；如果字符是加、减、乘或除号，则从运算符栈中弹出运算符和操作数，执行相应的运算，并将结果推入操作数栈中，直到运算符栈为空或栈顶运算符的优先级低于当前运算符的优先级。最后，操作数栈中剩下的唯一元素就是算术表达式的值。

数据结构 基于栈的算术表达式求值

### 使用栈数据结构实现算术表达式求值

为了直接处理中缀算术表达式而不将其转换为其他形式，可以采用双栈法。此方法涉及两个栈：一个是用于存储操作数的操作数栈(OPND)，另一个是用于存储运算符的运算符栈(OPTR)[^1]。

#### 初始化阶段
- 将`OPND`栈初始化为空。
- `OPTR`栈被初始化并放置一个特殊符号'#'表示表达式的起始标志[^2]。

#### 处理流程
当逐个字符解析给定的中缀表达式时：

对于遇到的操作数（即数字），应立即将其转化为浮点型数值并推入到`OPND`栈内。

面对非操作数情况，也就是遇到了运算符的时候，则需遵循如下逻辑：
- 对比新读取到的运算符与位于`OPTR`栈顶端的那个之间的优先级别；
- 如果新的运算符拥有更高的优先级，则它会被压入`OPTR`栈等待后续处理；
- 反之如果现有的栈顶运算符具有较高或相等的优先度，那么就应当先执行该次运算——具体做法是从`OPND`栈取出最近两次存入的操作数，并依据从`OPTR`弹出的运算符完成一次计算，之后把得到的结果重新送回至`OPND`栈顶部位置；
- 特殊情况下，若两者均为相同类型的括号（比如一对匹配的小括弧()），这表明子表达式的结束，此时仅需简单移除对应开闭括号而无需做任何实际运算。

最终，在整个字符串遍历完毕后，剩余在`OPND`栈上的唯一元素便是所求得的答案。

下面给出一段Python代码示例来展示这一过程:

def evaluate_expression(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    
    opnd_stack = []      # 操作数栈
    opt_stack = ['#']     # 运算符栈
    
    i = 0
    while i < len(expression) or opt_stack[-1] != '#':
        char = expression[i]

        if '0' <= char <= '9' or char == '.':
            num_str = ''
            while i < len(expression) and ('0' <= expression[i] <= '9' or expression[i] == '.'):
                num_str += expression[i]
                i += 1
            
            opnd_stack.append(float(num_str))
            continue
        
        elif char in '+-1]]:
                opt_stack.append(char)
            else:
                while precedence[char] <= precedence[opt_stack[-1]] and opt_stack[-1]!='#':
                    operator = opt_stack.pop()
                    operand2 = opnd_stack.pop()
                    operand1 = opnd_stack.pop()

                    result = apply_operator(operator, operand1, operand2)
                    opnd_stack.append(result)

                opt_stack.append(char)
        
        elif char == ')':
            top_opt = opt_stack.pop()
            while top_opt != '(':
                operand2 = opnd_stack.pop()
                operand1 = opnd_stack.pop()

                result = apply_operator(top_opt, operand1, operand2)
                opnd_stack.append(result)

                top_opt = opt_stack.pop()
                
        i+=1
                
    return opnd_stack[0]


def apply_operator(op, a, b):
    operations = {
        "+": lambda x,y : x+y,
        "-": lambda x,y : x-y,
        "*": lambda x,y : x*y,
        "/": lambda x,y : x/y
    }
    return operations[op](a,b)


if __name__ == "__main__":
    expr = "3 + (5 * 7 - 8 / 4)"
    print(f"The value of '{expr}' is {evaluate_expression(expr)}")