亲宝软件园·资讯

展开

Java栈的运用之中缀表达式求值详解

未见花闻 人气:0

栈运用题:中缀表达式求值

题目详情

给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

注意:

数据保证给定的表达式合法。

题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。

题目保证表达式中所有数字均为正整数。

题目保证表达式在中间计算过程以及结果中,均不超过 231−1。

题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1。

C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。

输入格式

共一行,为给定表达式。

输出格式

共一行,为表达式的结果。

数据范围

表达式的长度不超过105

输入样例:

(2+2)*(1+1)

输出样例:

8

解题思路

对于这道题,我们可以使用两个栈,一个栈nums用来存运算数,另外一个栈ops可以用来存运算符,但是运算符之间是存在优先级的,我们还可以使用一个哈希表来储存每个运算符的优先级,可以使用数字的大小表示优先级的高低。

第一步,遍历字符串,可能会遇到以下情况:

1)遇到数字,将数组储存到栈nums中。

2)遇到(,直接将(存到栈ops中。

3)遇到),取出栈顶两个数,取出栈顶运算符,进行运算,将运算结果存入栈nums中,如果栈ops栈顶不为空并且栈顶元素不为(,则继续运算,直到栈为空或者栈顶元素为(为止。

4)遇到运算符+,-,*,/,检查栈ops栈顶运算符优先级是否大于或等于遍历遇到的运算符,如果优先级大,则进行运算操作(同上取出栈nums两个数,栈ops一个操作符进行运算,并将结果储存到nums中),然后继续检查,直到栈ops为空或者ops栈顶元素为(,最后将遍历的运算符入栈ops。

第二步,检查是否运算完成。

字符串遍历完成后,此时运算不一定结束,检查栈ops是否为空,不为空继续进行运算操作,直到栈ops为空为止,最终nums剩余的一个数就是运算结果。

对于运算符优先级的判断我们可以通过建立哈希表,将运算符映射一个数字,其中数字越大就表示优先级越大。

实现代码

Java版本实现:

import java.util.*;

class Main {
    //栈nums 存运算数
    private static Deque<Integer> nums = new ArrayDeque<>();
    //栈ops 存运算符
    private static Deque<Character> ops = new ArrayDeque<>();
    
    //哈希表用来映射运算符优先级
    private static HashMap<Character, Integer> hash = new HashMap<>();
    
    //初始化哈希表
    static {
        hash.put('+', 1);
        hash.put('-', 1);
        hash.put('*', 2);
        hash.put('/', 2);
    }
    
    //判断某个字符是否是数字
    private static boolean isDigit(char c) {
        return c >= '0' &&c <= '9';
    }
    
    //实现运算方法
    private static void eval() {
        //去除第二个运算数
        int b = nums.pollLast();
        //取出第一个运算数
        int a = nums.pollLast();
        //取出运算符
        char op = ops.pollLast();
        
        //判断符号,对应进行运算
        if (op == '+') nums.offerLast(a + b);
        else if (op == '-') nums.offerLast(a - b);
        else if (op == '*') nums.offerLast(a * b);
        else if (op == '/') nums.offerLast(a / b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String s = sc.nextLine();
        
        char[] cs = s.toCharArray();
        
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            
            if (isDigit(c)) {
                //遍历的字符为数字,取出完整的数字放在数组当中
                int ret = c - '0';
                int j = i + 1;
                while (j < cs.length && isDigit(cs[j])) {
                    ret = ret * 10 + (cs[j] - '0');
                    j++;
                }
                //更新i
                i = j - 1;
                //将数字入栈
                nums.offerLast(ret);
            } else if (c == '(') {
                //遇到(,直接入栈ops
                ops.offerLast(c);
            } else if (c == ')') {
                //遇到),进行运算操作,直到栈顶遇到(为止
                while (!ops.isEmpty() && ops.peekLast() != '(') eval();
                //遇到(,将(出栈
                ops.pollLast();
            } else {
                //遇到运算符,则比较优先级,如栈顶运算符优先级大,则进行运算,直到栈为空或栈顶运算符较小或栈顶运算符为(
                while (!ops.isEmpty() && ops.peekLast() != '(' && hash.get(ops.peekLast()).compareTo(hash.get(c)) >= 0) eval();
                
                //将当前运算符入栈
                ops.offerLast(c);
            }
        }
        
        //检查ops栈内是否还有运算符,如果还有,则表示运算还没结束,继续运算,直到ops栈无运算符为止
        while (!ops.isEmpty()) eval();
        
        //输出nums栈顶元素,即是最终运算结果
        System.out.println(nums.peekLast());
    }
}

C++版本实现:

include <iostream>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

//栈1 存储元素
stack<int> nums;
//栈2 存储操作符号
stack<char> ops;


//哈希表 用来存储运算符优先级
unordered_map<char, int> pri = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

void eval()
{
    //取第二个操作数
    int b = nums.top();
    nums.pop();
    //取第一个操作数
    int a = nums.top();
    nums.pop();
    
    //取操作符
    char op = ops.top();
    ops.pop();
    
    //进行运算
    if (op == '+') nums.push(a + b);
    else if (op == '-') nums.push(a - b);
    else if (op == '*') nums.push(a * b);
    else if (op == '/') nums.push(a / b);
    
    //cout << a << " " << op << " " << b << "=";
    
    //cout << nums.top() << endl;
}

int main()
{
    string s;
    cin >> s;
    
    for (int i = 0; i < s.size(); i++) 
    {
        char c = s[i];
        if (isdigit(c)) 
        {
            //字符为数字,将该数字放入到储存数字的栈中
            int j = i + 1;
            int ret = s[i] - '0';
            while (j < s.size() && isdigit(s[j]))
            {
                ret = ret * 10 + (s[j] - '0');
                j++;
            }
            //更新i
            i = j  - 1;
            nums.push(ret);
        } else if (c == '(') 
        {
            ops.push(c);
        } else if (c == ')') 
        {
            //遇到右括号对栈元素进行运算,直到遇到(为止
            while (ops.size() > 0 && ops.top() != '(') eval();
            ops.pop();
        } else {
            //遇到运算符,比较优先级,如果优先级较高,则进行运算
            while (ops.size() > 0 && ops.top() != '(' && pri[ops.top()] >= pri[c]) eval();
            ops.push(c);
        }
    }
    
    //如果还有剩余运算符 则继续运算
    while (ops.size() > 0) eval();
    //栈顶元素即为最终的运算结果
    cout << nums.top() << endl;
    return 0;
}

加载全部内容

相关教程
猜你喜欢
用户评论