@chawuciren
2018-11-21T13:44:42.000000Z
字数 1094
阅读 709
leetcode
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
先初始化两个栈和一个队列,一个用来放数字,一个用来放符号。队列用来存放排好序的算式。
数字先进栈。碰到第一个符号,进符号的栈。然后按数字-符号-数字的顺序出栈并计算出表达式的值,将该值进队列。然后继续进栈,碰到第二个符号,如果队列不是空的,就将符号-数字进队列,计算出该表达式的值,往后以此类推。
输入的时候符号和数字混在一起,怎么实现输入?
好吧其实没有关系......一个char数组就搞定了
为了区分符号和数字(以下)
void judge(linklist* numnode,linklist *snode,char x){
if(x=='+'||x=='-'||x=='*'||x=='/'){
push(snode,x);
}
else{
push(numnode,x);
}
return;
}
void ergodicAll(linklist* numnode,linklist *snode,char array[],int len){
for(int i=0;i<len;i++){
judge(numnode,snode,array[i]);
}
return;
}
void ergodic(linklist *numnode){
while(!isEmpty(numnode)){
printf("%d",numnode->data);
numnode=numnode->next;
}
return;
}
void ergodic2(linklist *s){
while(!isEmpty(s)){
printf("%c",s->data);
s=s->next;
}
return;
}