1-(3+2)*7-9/3+(1+2)*3
和一般的简单计算不一样,这是一种混合运算甚至包含括号,所以我们的具体计算过程并不是从左到右的,而是有优先级判断的
基于这样一种情况,开始计算前作如下调整
将首尾各加一个符号用做识别,比如’#’,那么原式变成#1-(3+2)*7-9/3+(1+2)*3#,接下来初始化两个栈,stack1(用做存数字),stack2(用做存运算符)
首先将表达式第一个字符即#压入stack2,然后依次扫描表达式,遇到数字就直接压入stack1,若遇到运算符,作如下处理
将stack2栈顶的符号和扫描到的符号进行优先级判断:
若栈顶运算符的优先级低于刚扫描到的运算符的优先级,则让刚扫描到的运算符入栈
若栈顶运算符的优先级高于刚扫描到的运算符的优先级,则将stack2栈顶运算符退栈,同时stack1栈顶的数字连续退栈两次,将两个退栈的数字和一个退栈的运算符进行相应运算,将结果重新压入stack1(注意此时不一定能将刚扫描到的运算符入栈,有可能存在stack2栈顶连续多个运算符的优先级比刚扫描到的运算符优先级高,所以这一步需要一直计算到stack2栈顶运算符的优先级不比刚扫描到的运算符的优先级高为止,此时才能将刚扫描到的运算符压入stack2)
若栈顶运算符的优先级等于刚扫描到的运算符的优先级,则说明左右括号相遇,将stack2栈顶运算符退栈即可
重复以上操作,直到stack2栈顶元素和刚扫描到的运算符均为’#’时,说明表达式扫描完毕,此时stack1栈顶数字即为结果
算符优先关系如下图所示
最左边的一列为栈顶运算符,最上面的一行为刚扫描到的运算符,Error表示这两个运算符在表达式正常的情况下不会遇到,如果遇到可能是表达式有误
下面模拟一个最简单的例子的运行过程,例如3-2+4
首先将表达式变形为#3-2+4#,初始化stack1,stack2
#3-2+4#
#压入stack2
stack1 = []
stack2 = [#]
3-2+4#
3压入stack1
stack1 = [3]
stack2 = [#]
-2+4#
#和-判断优先级,# <-,-压入stack2
stack1 =[3]
stack2 = [#,-]
2+4#
2压入stack1
stack1 = [3,2]
stack2 = [#,-]
+4#
-和+判断,- >+,取出3,2和-,进行3-2运算将结果压入stack1
stack1 = [1]
stack2 = [#]
+4#
#和+判断,# <+,+压入stack2
stack1 = [1]
stack2 = [#,+]
4#
4压入stack1
stack1 = [1,4]
stack2 = [#,+]
#
+和#判断,+ >#,取出1,4和+,进行1+4运算将结果压入stack1
stack1 = [5]
stack2 = [#]
#
#和#相遇,表达式求值完毕,结果为stack1栈顶元素5
python源码
import re
def calculate(expression):
stack1 = []
stack2 = []
stack2.append('#')
expression = expression + '#'
for i in expression:
a = re.match(r'\d+',i)
if(a != None):
stack1.append(a.group(0))
else:
if(judgement(stack2[len(stack2)-1],i) == '<'):
stack2.append(i)
elif(judgement(stack2[len(stack2)-1],i) == '>'):
while(judgement(stack2[len(stack2)-1],i) == '>'):
operator = stack2.pop()
operand1 = stack1.pop()
operand2 = stack1.pop()
if(operator == '+'):
stack1.append(float(operand1) + float(operand2))
elif(operator == '-'):
stack1.append(float(operand2) - float(operand1))
elif(operator == '*'):
stack1.append(float(operand1) * float(operand2))
elif(operator == '/'):
stack1.append(float(operand2) / float(operand1))
if(i == ')'):
stack2.pop()
else:
stack2.append(i)
return stack1.pop()
def judgement(str1,str2):
dictionary1 = {'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'}
dictionary2 = {'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'}
dictionary3 = {'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'}
dictionary4 = {'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'}
dictionary5 = {'+':'<','-':'<','*':'<','/':'<','(':'<',')':'=','#':'error'}
dictionary6 = {'+':'>','-':'>','*':'>','/':'>','(':'error',')':'>','#':'>'}
dictionary7 = {'+':'<','-':'<','*':'<','/':'<','(':'<',')':'error','#':'='}
dictionary8 = {'+':dictionary1,
'-':dictionary2,
'*':dictionary3,
'/':dictionary4,
'(':dictionary5,
')':dictionary6,
'#':dictionary7}
return dictionary8[str1][str2]
a = '1-(3+2)*7-9/3+(1+2)*3'
print(calculate(a))
function test(){var txt1 = document.getElementById("txt1"),
txt2 = document.getElementById("txt2"),
txt3 = document.getElementById("txt3"),
opt = document.getElementById("sel")
txt3.value = eval(txt1.value + opt.value + txt2.value)//eval函数可计算某个字符串,并执行其中的的js代码
} <input type="text" id="txt1" />
<select id="sel">
<option value="+">+</option>
<option value="-">-</option>
<option value="*">*</option>
<option value="/">/</option>
</select>
<input type="text" id="txt2" />
=
<input type="text" id="txt3" />
<input type="button" id="btn" value="计算" onclick="test()"/>