赞
踩
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。
示例 1:
输入: "1 + 1"
输出: 2
示例 2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明:
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
思路分析:这种模拟计算器的题目难度不大,但是需要将逻辑理顺,思路要清晰,分好各种情况进行不同的处理。
class Solution { private: stack<int> dataStack;//数据栈 stack<char> operatorStack;//操作符栈 int sSize, tempValueOne, tempValueTwo; long long numRead; char operatorCh; public: void myOP() { //获取数据栈的栈顶两个元素,注意出栈顺序,先出的右操作数,后出的才是左操作数 tempValueTwo = dataStack.top(); dataStack.pop(); tempValueOne = dataStack.top(); dataStack.pop(); //获取操作符栈顶元素 operatorCh = operatorStack.top(); operatorStack.pop(); //进行运算,结果放回数据栈 switch (operatorCh) { case '-': dataStack.push(tempValueOne - tempValueTwo); break; case '+': dataStack.push(tempValueOne + tempValueTwo); break; default: break; } } int calculate(string s) { sSize = s.size(); for (int index = 0; index < sSize; ) {//扫描字符串 if (s[index] == ' ') {//如果是空格 index += 1; } else if (s[index] == '(' || s[index] == '+' || s[index] == '-') {//左括号、操作符直接进操作符栈 operatorStack.push(s[index++]); } else if (s[index] == ')') {//右括号需要判断栈顶是不是左括号 operatorStack.pop();//操作符栈顶的括号需要出栈 index += 1; //如果栈顶不是左括号,则需要将数据栈栈顶的两个元素进行运算 if (!operatorStack.empty() && operatorStack.top() != '(') { myOP();//进行一次运算操作 } } else { //读取一个操作数 numRead = 0; while (index < sSize && s[index] >= '0' && s[index] <= '9') { numRead = numRead * 10 + s[index++] - '0'; } dataStack.push(numRead); //如果操作符栈顶不是左括号 if (!operatorStack.empty() && operatorStack.top() != '(') { myOP();//进行一次运算操作 } } } while (!operatorStack.empty()) { myOP();//进行一次运算操作 } return dataStack.top(); } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。