Java栈的运用之中缀表达式求值详解
目录
- 栈运用题:中缀表达式求值
- 题目详情
- 解题思路
- 实现代码
栈运用题:中缀表达式求值
题目详情
给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-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剩余的一个数就是运算结果。
对于运算符优先级的判断AzTIKEQe我们可以通过建立哈希表,将运算符映射一个数字,其中数字越大就表示优先级越大。
实现代码
Java版本实现:
import java.util.*; class Main { //栈nums 存运算数 private static Deque<Integer> nums = new ArrayDeque<>(android); //栈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 <php;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 { //遇到运算符,比较优先级,如果优先级较高,则进行运算 开发者_Go培训 while (ops.size() > 0 && ops.top() != '(' && pri[ops.top()] >= pri[c]) eval(); ops.push(c); } } //如果还有剩余运算符 则继续运算 while (ops.size() > 0) eval(); //栈顶元素即为最终的运算结果 cout << nums.AzTIKEQetop() << endl; return 0; }
以上就是Java栈的运用之中缀表达式求值详解的详细内容,更多关于Java中缀表达式求值的资料请关注我们其它相关文章!
精彩评论