建设行政主管部门查询网站,饮食网站开发需求,帝国cms模板网,网站专栏建设情况这是一道 困难 题。 题目来自#xff1a;leetcode 题目
给你一个字符串表达式 s #xff0c;请你实现一个基本计算器来计算并返回它的值。
注意: 不允许使用任何将字符串作为数学表达式计算的内置函数#xff0c;比如 eval() 。
提示#xff1a;
s 由数字、‘’、‘-’… 这是一道 困难 题。 题目来自leetcode 题目
给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。
注意: 不允许使用任何将字符串作为数学表达式计算的内置函数比如 eval() 。
提示
s 由数字、‘’、‘-’、‘(’、‘)’、和 ’ ’ 组成s 表示一个有效的表达式‘’ 不能用作一元运算(例如 “1” 和 “(2 3)” 无效)输入中不存在两个连续的操作符每个数字和运行的计算将适合于一个有符号的 32位 整数
示例 1
输入s 1 1
输出2示例 2
输入s 2-1 2
输出3示例 3
输入s (1(452)-3)(68)
输出23解题思路
这道题是 实现一个包含“加减乘除”的基本计算器 的扩展在表达式中增加了 括号 “(”, “)” 和 正负数但是删除了 “*” 和 “/”。
在原来的解题方法中补充以下几点
括号的处理 如果遇到左括号直接压入操作符栈。如果遇到右括号将操作符栈中左括号后面的所有操作符出栈并与数字栈进行计算合并。 正负数的处理 可以使用 补0 的思路在正负数前面加一个“0”将表达式转换为没有正负号的式子。
那么如何确定“”和“-”是代表算符还是正负号呢
如果 “”和“-” 是第一个非空字符那么代表是正负号。如果 “”和“-” 的前一个非空字符也是“”或者“-”那么代表是正负号。如果 “”和“-” 的前一个非空字符是 左括号 那么代表是正负号。
注补0的思路只能用于加减法.
代码实现 class Solution {private DequeInteger numStack new LinkedList();private DequeCharacter optStack new LinkedList();public int calculate(String s) {int n s.length();boolean needZero true;for(int i 0; i n; i){char ch s.charAt(i);if(this.isNumber(ch)){int num 0;needZero false;while(i n this.isNumber(s.charAt(i))){num num * 10 s.charAt(i) - 0;i;}numStack.push(num);i--;}else if(ch ){continue;}else if(ch (){optStack.push(();needZero true;continue;}else if(ch )){while(optStack.peek() ! (){this.calc(numStack, optStack);}// 删除左括号optStack.pop();needZero false;}else{if(needZero){numStack.push(0);}while(!optStack.isEmpty() optStack.peek() ! (){this.calc(numStack, optStack);}optStack.push(ch);needZero true;}}while(!optStack.isEmpty()){this.calc(numStack, optStack);}return numStack.pop();}private boolean isNumber(char ch){return ch 0 ch 9;}private void calc(DequeInteger numStack, DequeCharacter optStack){int num2 numStack.pop();int num1 numStack.pop();char opt optStack.pop();if(opt ){ numStack.push(num1 num2);}else{numStack.push(num1 - num2);}}}复杂度分析
时间复杂度O(N)O(N)O(N)N 为字符串长度。
空间复杂度O(N)O(N)O(N)N 为字符串长度。
